(BOJ) 13460 구슬 탈출 2

문제: https://www.acmicpc.net/problem/13460

- dfs로 풀었다.

소스 코드:

#include <iostream> #include <vector> #include <map> #include <queue> #include <string> #include <string.h> #include <algorithm> #define inf 100 using namespace std; int n, m,result=inf; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; char arr[11][11]; void func(int rx, int ry, int bx, int by,int d,int cnt) { if (cnt == 11) return; bool frag=false;    // 빨간 공이 구멍에 들어갔는지 확인하는 변수 bool move = false;    // 한번이라도 이동했는지 확인하는 변수 while (1) { if (!frag&&arr[rx + dx[d]][ry + dy[d]] == 'O') {    // 빨간 공이 구멍에 들어가도 파란 공이 들어갈 수도 있으므로                                                                                    파란 공은 계속 이동 시킨다 (이동 가능할 때) rx =ry= 0; frag = true; move = true; continue; } else if (rx + dx[d] == bx && ry + dy[d] == by) {}  // 앞으로 갈 곳에 파란 공이 위치해있으면 이동 불가 else if (arr[rx + dx[d]][ry + dy[d]] == '.' ) { rx += dx[d]; ry += dy[d]; move = true; continue; } if (arr[bx + dx[d]][by + dy[d]] == 'O') return;  // 파란 공이 구멍에 들어가면 현재 경로로는 탈출 실패 -> 바로 return else if (bx + dx[d] == rx && by + dy[d] == ry) {}  // 앞으로 갈 곳에 빨간 공이 위치해있으면 이동 불가 else if (arr[bx + dx[d]][by + dy[d]] == '.') { bx += dx[d]; by += dy[d]; move = true; continue; } if(!move) return;      // 한번도 안 움직이면 최소 횟수가 아니므로  return  break; } if (frag) { result = min(result, cnt); return; } for (int i = 0; i < 4; i++) { if (i == d) continue;  // 같은 방향으로 갈 필요 없음 func(rx, ry, bx, by, i, cnt + 1); } } int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m; int q, w, e, r; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> arr[i][j]; if (arr[i][j] == 'R') { q = i, w = j; arr[i][j] = '.'; } else if (arr[i][j] == 'B') { e = i, r = j; arr[i][j] = '.'; } } } for (int i = 0; i < 4; i++) { func(q, w, e, r, i, 1); } if (result == inf) cout << "-1\n"; else cout << result << '\n'; return 0; }