#include <iostream> #include <cstring> #include <stdlib.h> #include <queue> using namespace std; typedef struct _path { int x; int y; int s; }path; queue<path> tradition; int dir[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 }; int book[1005][1005]; char map[1005][1005]; int n, m, r, c; int travel(char flag) { path start, element, temp; start.x = 0; start.y = 0; start.s = 1; tradition.push(start); while (tradition.size()) { element = tradition.front(); tradition.pop(); for (int i = 0; i < 4; i++) { int dx = element.x + dir[i][0]; int dy = element.y + dir[i][1]; if (dx >= 0 && dx < n && dy >= 0 && dy < m) { if (map[dx][dy] == '.' || map[dx][dy] == flag) { if (book[dx][dy] == 0) { book[dx][dy] = 1; temp.x = dx; temp.y = dy; temp.s = element.s + 1; tradition.push(temp); } if (dx == r && dy == c) { return (element.s) * 2; } } } } } return 6565656; } int main() { int T; cin >> T; while (T--) { memset(book, 0, sizeof(book)); cin >> n >> m >> r >> c; r--, c--; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } int min1 = travel('F'); int min2 = travel('M'); int ans = min(min1, min2); if (ans == 6565656) { cout << "IMPOSSIBLE" << endl; } else { cout << ans << endl; } } return 0; }
全部评论
(0) 回帖