Untitled
unknown
plain_text
a year ago
1.8 kB
2
Indexable
Never
#include <iostream> using namespace std; const int MAX_SIZE = 201; const int INF = 1000000; int in[MAX_SIZE][MAX_SIZE]; int dem[MAX_SIZE][MAX_SIZE]; int Qx[MAX_SIZE * MAX_SIZE]; int Qy[MAX_SIZE * MAX_SIZE]; int Qd[MAX_SIZE * MAX_SIZE]; int r, f; int dx[] = {1, 0, 0, -1}; int dy[] = {0, 1, -1, 0}; void push(int x, int y, int d) { r++; Qx[r] = x; Qy[r] = y; Qd[r] = d; } void pop(int &x, int &y, int &d) { f++; x = Qx[f]; y = Qy[f]; d = Qd[f]; } int BFS(int x, int y, int a, int b, int n) { r = -1; f = -1; push(x, y, 0); while (r != f) { int cx, cy, cd; pop(cx, cy, cd); for (int i = 0; i < 4; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && in[nx][ny] == 1) { push(nx, ny, cd + 1); in[nx][ny] = 0; dem[nx][ny] = cd + 1; if (nx == a && ny == b) return dem[nx][ny]; } } } return -1; } int main() { int T; cin >> T; while (T--) { int n; cin >> n; int x, y; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> in[i][j]; dem[i][j] = INF; if (in[i][j] == 2) { x = i; y = j; } } } int d1 = BFS(1, 1, x, y, n); int d2 = BFS(x, y, n, n, n); if (d1 == -1 || d2 == -1) { cout << -1 << endl; } else { cout << d1 + d2 << endl; } } return 0; }