Untitled

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