princess-fix

#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;
}