Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
4.6 kB
1
Indexable
Never
#include<iostream>

using namespace std;

int main_result[50][7], _p_result[4];
int map_way[30][30], visit[30][30];
int G, N;
pair<int, int> Oxy[4]={make_pair(-1,0), make_pair(0,1), make_pair(1,0), make_pair(0,-1)};

struct node{
    int r, c;
} Queue[500];
int front, rear;
void init(){
    front = rear = -1;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            visit[i][j]=1000000;
}
void push(int r, int c){
    rear++;
    Queue[rear].r = r;
    Queue[rear].c = c;
}
node pop(){
    return Queue[++front];
}
bool isEmpty(){
    return front==rear;
}

node mine[4];

int bfs(int x, int y, int kk){
    // BFS
    init();
    visit[x][y] = 0;
    push(x, y);
    int _cnt = 0;
    while(!isEmpty())
    {
        node cur = pop();
        if(cur.r==mine[kk].r && cur.c==mine[kk].c) 
            return visit[cur.r][cur.c];
        for(int i=0; i<4; i++)
        {
            int tempx = cur.r+Oxy[i].first;
            int tempy = cur.c+Oxy[i].second;
            if(tempx>=1 && tempx<=N && tempy>=1 && tempy<=N && visit[tempx][tempy]==1000000 && map_way[tempx][tempy]!=0){
                push(tempx, tempy);
                visit[tempx][tempy] = visit[cur.r][cur.c] + 1;
            }
        }
        _cnt++;
        if(_cnt==3*N) return 0;
    }
    return 0;
}
int main()
{
    int T;
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    freopen("input.txt", "r", stdin);
    cin >> T;

    for(int test_case = 1; test_case <= T; ++test_case)
    {
        //reset
        main_result[0][0]=0;

        cin >> N >> G;
        //doc vi tri mo vang
        for(int i=0; i<G; i++)
            cin >> mine[i].r >> mine[i].c;
        //doc map duong di
        for(int ii=1; ii<=N; ii++)
            for(int jj=1; jj<=N; jj++)
                cin >> map_way[ii][jj];

        for(int i=0; i<G; i++)
            map_way[mine[i].r][mine[i].c]=2;

        int q=0;
        int u=0, sum=0, _max=0, best_u=0;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                u=0; sum=0; _max=0;
                //k phai vang vs k phai da
                if(map_way[i][j]==1){
                    for(int k=0; k<G; k++){
                        int kq = bfs(i, j, k);
                        if(kq>0){
                            u+=1;
                            _p_result[k]=1;
                        }else{
                            _p_result[k]=0;
                            continue;
                        }
                        if(kq>_max) _max = kq;
                        sum+=kq;
                    }
                    if(u>0){
                        if(u > best_u) best_u=u;
                        if(u>=best_u && q>0){
                            main_result[q][0] = u;
                            main_result[q][1] = sum;
                            main_result[q][2] = _max;
                            for(int aa=0; aa<G; aa++)
                                main_result[q][3+aa]=_p_result[aa];
                            q++;
                        } else if(q==0){ //first
                            main_result[q][0] = u;
                            main_result[q][1] = sum;
                            main_result[q][2] = _max;
                            for(int aa=0; aa<G; aa++)
                                main_result[q][3+aa]=_p_result[aa];
                            q++;
                        }
                    }
                }
            }
        }
        //read data & print
        if(best_u==0)
            cout << "Case #" << test_case << endl << -1 << endl;
        else{
            int best_answer=10000, index;
            for(int aa=0; aa<q; aa++){
                if(main_result[aa][0]==best_u && main_result[aa][2] < best_answer){
                    best_answer = main_result[aa][2];
                    index = aa;
                }
            }
            if(best_u==G)
                cout << "Case #" << test_case <<  endl << main_result[index][2] << endl;
            else{
                cout << "Case #" << test_case <<  endl << main_result[index][2] << endl;
                for(int _ct=0; _ct<G; _ct++){
                    if(main_result[index][3+_ct]==0){
                        cout << mine[_ct].r << " " << mine[_ct].c << endl;
                    }
                }
            }

        }
    }
    return 0;//Your progrsam should return 0 on normal termination.
}
Leave a Comment