Untitled

#include <iostream>
#include <utility>

using namespace std;

const int MAX_N = 30;
const int MAX_M = MAX_N * MAX_N;

// Tính khoảng cách ngắn nhất từ start đến ground
int shortestPath(int grid[MAX_N][MAX_N], pair<int, int> start, int N) {
    int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    pair<pair<int, int>, int> q[MAX_M];
    int front = 0, rear = 0;
    q[rear++] = {start, 0};
    bool visited[MAX_N][MAX_N] = {false};
    visited[start.first][start.second] = true;

    while (front < rear) {
        auto frontNode = q[front++];
        int x = frontNode.first.first;
        int y = frontNode.first.second;
        int dist = frontNode.second;

        if (grid[x][y] == 0) {
            return dist;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + directions[i][0];
            int ny = y + directions[i][1];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q[rear++] = {{nx, ny}, dist + 1};
            }
        }
    }
    return -1; // Không thể đạt được mặt đất
}

// Tìm số lượng cm khối đất ít nhất cần đào để thoát khỏi khối đất
int minDiggingNeeded(int grid[MAX_N][MAX_N], int N) {
    pair<int, int> start;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (grid[i][j] == 2) {
                start = {i, j};
                break;
            }
        }
    }

    int minDigging = INT_MAX;
    minDigging = min(minDigging, shortestPath(grid, start, N));

    return minDigging;
}

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        int N;
        cin >> N;

        int grid[MAX_N][MAX_N];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cin >> grid[i][j];
            }
        }

        int minDigging = minDiggingNeeded(grid, N);
        cout << "#" << t << " " << minDigging << endl;
    }

    return 0;
}