hugo dao vang 1

#include <iostream>

using namespace std;

int A[22][22];
int visit[22][22];
int visitA[5];
int G[3][5];
int M,N;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int front, rear;
int ans;
int re;

struct Node{
    int r,c;
};

Node queue[100000];

void enQueue(int x, int y){
    Node node; node.r = x; node.c = y;
    rear++;
    queue[rear] = node;
}

Node deQueue(){
    front++;
    return queue[front];
}

int findMax(){
    int max = visit[G[0][0]][G[1][0]];
    for (int i = 1; i < N; i++)
    {
        if(visit[G[0][i]][G[1][i]] > max){
            max = visit[G[0][i]][G[1][i]];
        }
    }
    return max - 1;
}

void reSetvisit(){
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if(A[i][j] == 0){
                visit[i][j] = -1;
            }else
            {
                visit[i][j] = 0;
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        G[2][i] = 0;
    }
}

void BFS(int x, int y){
    reSetvisit();
    front = rear = -1;
    enQueue(x,y);
    visit[x][y] = 1;
    int cnt = 0;
    while (rear != front)
    {
        if(cnt == N){
            break;
        }
        Node mid = deQueue();
        for (int i = 0; i < N; i++)
        {
            if(mid.r == G[0][i] && mid.c == G[1][i]){
                cnt++;
                G[2][i] = 1;
            }
        }

        for (int i = 0; i < 4; i++)
        {
            int tx = mid.r + dx[i];
            int ty = mid.c + dy[i];
            if (tx > 0 && tx <= M && ty > 0 && ty <= M && visit[tx][ty] == 0)
            {
                enQueue(tx,ty);
                visit[tx][ty] = visit[mid.r][mid.c] + 1;
            }
        }
    }

    if(cnt > ans){
        ans = cnt;
        for (int i = 0; i < N; i++)
        {
            visitA[i] = G[2][i];
        }
        re = findMax();
    } else if (cnt == ans)
    {
        int tmp = findMax();
        if(re > tmp){
            re = tmp;
            for (int i = 0; i < N; i++)
            {
                visitA[i] = G[2][i];
            }
        }
    }


}


int main(){
    int tc, T;
    freopen("input.txt", "r", stdin);

    cin>> T;
    for (tc = 1; tc <= T; tc++)
    {
        cin>> M >> N;
        ans = re = 0;
        for (int i = 0; i < N; i++)
        {
            cin >> G[0][i] >> G[1][i];
        }

        for (int i = 1; i <= M; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                cin>> A[i][j];
            }
        }
        for (int i = 0; i < N; i++)
        {
            A[G[0][i]][G[1][i]] = 3;
        }
        int check = 1;
        for (int i = 0; i < N; i++)
        {
            if(check == 0){
                break;
            }
            for (int j = 0; j < 4; j++)
            {
                int tx = G[0][i] + dx[j];
                int ty = G[1][i] + dy[j];
                if (tx >= 1 && tx <= M && ty >=1 && ty <= M && A[tx][ty] == 1)
                {
                    check = 0;
                }
            }
        }
        if(check == 1){
            cout<< "Case #" << tc << endl;
            cout<< "-1" << endl;
            continue;
        }

        for (int i = 1; i <= M; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                if(A[i][j] == 1){
                    BFS(i,j);
                }
            }
        }

        cout<< "Case #" << tc << endl;
        cout<< re << endl;
        for (int i = 0; i < N; i++)
        {
            if(visitA[i] == 0){
                cout<<G[0][i] << " " << G[1][i] << endl;
            }
        }


    }

    return 0;
}