princess-fix
unknown
plain_text
6 months ago
2.0 kB
0
Indexable
Never
#include <iostream> using namespace std; const int MAX_SIZE = 201; const int INF = 1e9; 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 dx[] = {1, 0, 0, -1}; int dy[] = {0, 1, -1, 0}; void push(int x, int y, int d, int &r) { r++; Qx[r] = x; Qy[r] = y; Qd[r] = d; } void pop(int &x, int &y, int &d, int &f) { f++; x = Qx[f]; y = Qy[f]; d = Qd[f]; } int BFS(int startX, int startY, int endX, int endY, int n) { int r = -1, f = -1; push(startX, startY, 0, r); while (r != f) { int x, y, d; pop(x, y, d, f); if (x == endX && y == endY) { return dem[x][y]; } for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && in[nx][ny] != 0 && dem[nx][ny] == INF) { push(nx, ny, d + 1, r); dem[nx][ny] = d + 1; } } } return -1; } int main() { freopen("input.txt","r",stdin); int T; cin >> T; while (T--) { int n; cin >> n; int startX, startY; 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) { startX = i; startY = j; } } } int d1 = BFS(1, 1, startX, startY, n); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dem[i][j] = INF; } } int d2 = BFS(startX, startY, n, n, n); if (d1 == -1 || d2 == -1) { cout << -1 << endl; } else { cout << d1 + d2 << endl; } } return 0; }