Untitled

 avatar
unknown
plain_text
2 years ago
2.1 kB
5
Indexable
#include<iostream>

using namespace std;

int q[6000]={0}, f=-1, r=-1;
int d[8][10]={{-1,0,1,0,0,-1,0,1},{-1,0,1,0,0,-1,0,1},{-1,0,1,0},{0,-1,0,1},{-1,0,0,1},{1,0,0,1},{1,0,0,-1},{-1,0,0,-1}};
int dsize[] = {8, 8, 4, 4, 4, 4, 4, 4};
int a[1000][1000]={0}, dd[1000][1000]={0};

void enqueue(int x, int y){
    q[++r]=x; q[++r]=y;
}

int dequeue(){
    return q[++f];
}

bool isEmpty(){
    return f==r;
}

int main(){
    ios::sync_with_stdio(false);

	freopen("pipe.txt", "r", stdin);

    int t, tc;
    cin >> t;
    for(int tc=1; tc<=t; tc++){
        int n, m, gx, gy, li, ans = 0;
        cin >> n >> m >> gx >> gy >> li;
        f=-1; r=-1;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin >> a[i][j];
                dd[i][j]=0;
            }
        }
        enqueue(gx, gy); dd[gx][gy]=1;
        int cur = 1;
        while(!isEmpty()){
            int x = dequeue(), y = dequeue();
            for(int i=0;i<dsize[a[x][y]];i+=2){
                int dx = d[a[x][y]][i], dy = d[a[x][y]][i+1];
                int px = x + dx, py = y+dy;
                if(px <0 || px >=n || py<0 || py>=m) continue;
                else {
                    if(a[px][py]!=0 && dd[px][py] ==0){
                        bool connect=false;
                        int pipe = a[px][py];
                        for(int j=0; j<dsize[a[px][py]]; j+=2) {
                            if(d[pipe][j]==-dx && d[pipe][j+1]==-dy){
                                connect = true;
                                break;
                            }
                        }
                        if(connect){
                            dd[px][py]=dd[x][y]+1;
                            enqueue(px, py);
                        }
                    }
                }
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m;j++)
                if(dd[i][j]<=li && dd[i][j]>0) ans++;
        }

        cout << "Case #" << tc << "\n" << ans << endl;
    }
}
Editor is loading...