// #16197 두 동전 //동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다. //동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다. //그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. //이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다. #include <iostream> #include <queue> #include <cstring> using namespace std; int dir[4][2] = { {1,0}, { 0,1 }, { -1,0 }, { 0,-1 } }; int n, m; char map[22][22]; int visit[21][21][21][21]; typedef struct xy { int x, y; }; typedef struct info { int x1, y1; int x2, y2; }; xy st[2]; bool move(int*x1, int*y1, int*x2, int*y2,int d,int TIME) { //코인 1 먼저 그다음 코인 2 int sum = 0;//떨어진 횟수 if (*x1 < 0 || *y1 < 0 || *x1 >= n || *y1 >= m) { sum++; } else if (map[*x1][*y1] == '#') { *x1 -= dir[d][0], *y1 -= dir[d][1]; } if (*x2 < 0 || *y2 < 0 || *x2 >= n || *y2 >= m) { sum++; } else if (map[*x2][*y2] == '#') { *x2 -= dir[d][0], *y2 -= dir[d][1]; } //둘다 움직일 수 있는 경우 //둘다 떨어지거나 포개질 경우 if (*x1 == *x2&&*y1 == *y2||sum==2)return false; else if (sum == 1) { //하나만 떨어질 경우 cout << TIME+1 << endl; exit(0); } return true; } void bfs() { queue<info>q; q.push({ st[0].x,st[0].y,st[1].x,st[1].y }); visit[st[0].x][st[0].y][st[1].x][st[1].y] = true; int TIME = 0; while (!q.empty()) { int sz = q.size(); while (sz--) { int fx1 = q.front().x1, fy1 = q.front().y1; int fx2 = q.front().x2, fy2 = q.front().y2; q.pop(); //cout << "fx1 " << fx1 << " fy1 " << fy1 << " fx2 " << fx2 << " fy2 " << fy2 << endl; for (int d = 0; d < 4; d++) { int nx1 = fx1 + dir[d][0], ny1 = fy1 + dir[d][1]; int nx2 = fx2 + dir[d][0], ny2 = fy2 + dir[d][1]; bool tf=move(&nx1, &ny1, &nx2, &ny2,d,TIME); if (!tf)continue; if (visit[nx1][ny1][nx2][ny2])continue; visit[nx1][ny1][nx2][ny2] = true; q.push({ nx1,ny1,nx2,ny2 }); } } TIME++; if (TIME >= 10)break; } cout << -1 << endl; } int main() { cin >> n >> m; int idx = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; if (map[i][j] == 'o') { st[idx++] = { i,j }; } } } bfs(); }