14497번: 주난의 난(難)
주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N*M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로 친구들을 쓰러뜨릴(?) 때 까지 계속해서 퍼져나간다. 다르게 표현해서, 한 번의 점프
www.acmicpc.net
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int N, M, X1, Y1, X2, Y2;
string map[300];
queue<pair<int, int>> q;
bool vst[300][300];
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
bool dfs(int r, int c, int t) {
vst[r][c] = 1;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (0 <= nr && nr < N && 0 <= nc && nc < M && !vst[nr][nc]) {
switch(map[nr][nc]){
case '1':
q.push(make_pair(nr, nc));
break;
case '0':
if (dfs(nr, nc, t)) {
return 1;
}
break;
case '#':
return 1;
}
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> X1 >> Y1 >> X2 >> Y2;
q.push(make_pair(X1 - 1, Y1 - 1));
for (int r = 0; r < N; ++r) {
cin >> map[r];
}
for (int t = 0; !q.empty(); ++t) {
int qs = q.size();
while (qs--) {
int r = q.front().first, c = q.front().second;
q.pop();
map[r][c] = '0';
if (!vst[r][c]) {
if (dfs(r, c, t)) {
cout << t + 1;
goto out;
}
}
}
}
out:
return 0;
}