Submission

PPPPPPPPPPP

Score: 100

User: Monasm

Problemset: ต่อท่อน้ำเลี้ยง

Language: cpp

Time: 0.404 second

Submitted On: 2024-11-13 01:36:16

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int gy[] = {0,1,0,-1};
int gx[] = {-1,0,1,0};

int find(vector<int> &p,int x){
    if (p[x]!=x)p[x]=find(p,p[x]); 
    return p[x];
}

void super_por(vector<int> &p,int a,int b){
    a=find(p,a);
    b=find(p,b);
    if(a!=b)p[a]=b;
}

int main() {
    int n,m;cin>>n>>m;
    int adj[n][m],vis[n][m];
    vector<int> p(n*m);
    for(int i=0;i<n*m;i++){
        p[i]=i;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char c;cin >> c;
            int x = c;
            x = x>='A'?x-'A'+10:x-'0';
            adj[i][j] = x;
            vis[i][j] = 0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!vis[i][j]){
                vis[i][j] = 1;
                queue<pii> q;
                q.push({i,j});
                while(!q.empty()){
                    int nx = q.front().first;
                    int ny = q.front().second;
                    q.pop();
                    vis[nx][ny] = 1;
                    int ox = adj[nx][ny],a[4];
                    for(int k=0;k<4;k++){
                        a[k] = (ox&1);
                        ox=(ox>>1);
                        if(a[k]){
                            int x = nx+gx[k];
                            int y = ny+gy[k];
                            if(!(0<=x&&x<n&&0<=y&&y<m)){
                                continue;
                            }
                            int b[4],oy = adj[x][y];
                            for(int l=0;l<4;l++){
                                b[l] = (oy&1);
                                oy=(oy>>1);
                            }
                            if(b[(k+2)%4]==a[k]&&vis[x][y]==0){
                                vis[x][y] = 1;
                                super_por(p,(m*nx)+ny,(m*x)+y);
                                q.push({x,y});
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<n*m;i++){
        find(p,i);
    }
    int t;cin >> t;
    while(t--){
        int a,b,c,d;cin>>a>>b>>c>>d;
        if(find(p,(m*a)+b)==find(p,(m*c)+d)){
            cout<<"Y"<<endl;
        }
        else{
            cout<<"N"<<endl;
        }
    }
}