[백준] 8972번 미친 아두이노(c++)
[백준] 8972번 미친 아두이노
문제 링크: https://www.acmicpc.net/problem/8972
문제
입출력
풀이
구현, 시뮬레이션 문제였다.
먼저 종수의 아두이노를 움직이고, 미친 아두이노와 겹치지 않는지 체크를 한다.
만약 위에서 겹친다면 game over
그 후에 미친 아두이노들을 다 움직인다.
종수의 아두이노와 겹친 아두이노가 있는지 체크.
-> 만약 있다면 game over.
-> 없다면, 겹친 미친 아두이노가 있는지 체크하고 해당 칸에 모든 아두이노를 없앤다.
나는 종수의 아두이노를 1 빈칸을 0 미친 아두이노를 2로 표현을 해서, 움직일 때 각 칸의 값을 더해서 겹치는 여부를 체크해서 문제를 풀었다.
꼼꼼하게 조건들을 다 체크하고 풀어야지 시간이 오래 안걸리는데, 그런 점이 부족했다.
코드(c++)
#include <iostream>
#include <vector>
#include <string>
#define MAX 987654321
using namespace std;
int R, C;
int map[101][101];
vector<pair<int,int> > insaneAdu;
pair<int,int> jongsuAdu;
int mX[] = {1,1,1,0,0,0,-1,-1,-1};
int mY[] = {-1,0,1,-1,0,1,-1,0,1};
int distDiff(int x, int y){
return abs(jongsuAdu.first - x) + abs(jongsuAdu.second - y);
}
void bomb(){
vector<pair<int,int> > alive;
vector<pair<int,int > > bombLoc;
for(int i = 0 ; i <insaneAdu.size() ; i++){
if(map[insaneAdu[i].first][insaneAdu[i].second] != 2) bombLoc.push_back(make_pair(insaneAdu[i].first,insaneAdu[i].second));
else alive.push_back(make_pair(insaneAdu[i].first, insaneAdu[i].second));
}
for(int i = 0 ; i < bombLoc.size() ; i++){
map[bombLoc[i].first][bombLoc[i].second] = 0;
}
insaneAdu = alive;
}
bool checkDone(pair<int,int> a){
if(map[a.first][a.second] == 0 || map[a.first][a.second] == 1 || map[a.first][a.second] % 2 == 0 ) return false;
return true;
}
bool insaneMoveAndCheckDone(){
for(int i = 0 ; i < insaneAdu.size() ; i++){
int minDist = distDiff(insaneAdu[i].first,insaneAdu[i].second);
int idx = 4;
for(int j = 0 ; j < 10 ; j++){
int nX = insaneAdu[i].first + mX[j]; int nY = insaneAdu[i].second + mY[j];
if(nX < 0 || nX >= R || nY <0 || nY >= C) continue;
int tmp = distDiff(nX,nY);
if(minDist > tmp){
minDist = tmp;
idx = j;
}
}
// move
map[insaneAdu[i].first][insaneAdu[i].second] -= 2;
map[insaneAdu[i].first + mX[idx]][insaneAdu[i].second + mY[idx]] += 2;
insaneAdu[i].first += mX[idx]; insaneAdu[i].second += mY[idx];
}
for(int i = 0 ; i < insaneAdu.size() ; i++){
if(checkDone(insaneAdu[i])) return true;
}
bomb();
return false;
}
bool jonsuMoveAndCheckDone(int n){
int nX = jongsuAdu.first + mX[n] ; int nY = jongsuAdu.second + mY[n];
map[nX][nY] += 1;
map[jongsuAdu.first][jongsuAdu.second] -= 1;
jongsuAdu = make_pair(nX,nY);
return false;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> R >> C;
for(int i = 0 ; i < R ; i++){
string temp;
cin >> temp;
for(int j = 0 ; j < C ; j++){
if(temp[j] == 'I') {
map[i][j] = 1;
jongsuAdu = make_pair(i,j);
}
else if(temp[j] == 'R') {
map[i][j] = 2;
insaneAdu.push_back(make_pair(i,j));
}
else map[i][j] = 0;
}
}
string order;
cin >> order;
int res = 0;
bool isDone = false;
for(int i = 0 ; i < order.length() ; i++){
res++;
if(jonsuMoveAndCheckDone((order[i] - '0') - 1)) {
isDone = true;
break;
}
if(insaneMoveAndCheckDone()){
isDone = true;
break;
}
}
if(isDone) cout << "kraj " << res << "\n";
else{
for(int i = 0 ; i < R ; i++){
string tmp = "";
for(int j = 0 ; j < C ; j++){
if(map[i][j] == 1) tmp += 'I';
else if(map[i][j] == 2) tmp += 'R';
else tmp += '.';
}
cout << tmp << "\n";
}
}
}
Author And Source
이 문제에 관하여([백준] 8972번 미친 아두이노(c++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kpg0518/백준-8972번-미친-아두이노c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)