두 동전

 

*두 동전이 모두 보드 바깥으로 나가는 경우 -> continue;

*모두 보드안으로 이동하는 경우 

-둘 다 벽인 경우 continue;

-하나만 벽인 경우 -> 그 동전은 이동하지 않고 머무른다. 

#include <iostream> #include <vector> #include <queue> #include <algorithm> #define INF 987654321 using namespace std; typedef struct Pos { int x, y; }; typedef struct Coin { //int cnt; Pos one; Pos two; }; int n, m; char map[21][21]; Pos coin1, coin2; int ans = INF; bool visited[21][21][21][21]; int dx[4] = { -1,0,0,1 }, dy[4] = { 0,-1,1,0 }; bool check(int x, int y, int dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) return false; return true; } void playGame() { queue<Coin> q; q.push({coin1, coin2 }); visited[coin1.x][coin1.y][coin2.x][coin2.y] = true; int limit = 0; while (!q.empty()) { int size = q.size(); ++limit; if (limit > 10) break; while (size--) { Pos c1 = q.front().one; Pos c2 = q.front().two; //int times = q.front().cnt; q.pop(); for (int i = 0; i < 4; i++) { int c1nx = c1.x; int c1ny = c1.y; int c2nx = c2.x; int c2ny = c2.y; if (check(c1nx, c1ny, i)) { if (check(c2nx, c2ny, i)) { //둘 다 이동 c1nx = c1.x + dx[i]; c1ny = c1.y + dy[i]; c2nx = c2.x + dx[i]; c2ny = c2.y + dy[i]; //둘 중 하나가 벽이라면 하나만 이동한다. if (map[c1nx][c1ny] == '#') { c1nx = c1.x; c1ny = c1.y; } if (map[c2nx][c2ny] == '#') { c2nx = c2.x; c2ny = c2.y; } if (visited[c1nx][c1ny][c2nx][c2ny] ) continue; visited[c1nx][c1ny][c2nx][c2ny] = true; q.push({ Pos{c1nx, c1ny}, Pos{c2nx, c2ny} }); } else { //한 동전만 빠짐 c1nx = c1.x + dx[i]; c1ny = c1.y + dy[i]; ans = min(ans, limit); } } else { if (check(c2nx, c2ny, i)) { //한 동전만 빠짐 c2nx = c2.x + dx[i]; c2ny = c2.y + dy[i]; ans = min(ans, limit); } //둘 다 빠지면 아무것도 안함 } } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; bool flag = false; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; if (map[i][j] == 'o') { if (!flag) { flag = true; coin1 = Pos{ i, j }; } else coin2 = Pos{ i, j }; } } } playGame(); if (ans == INF) cout << -1 << '\n'; else cout << ans << '\n'; return 0; }