100 但是 MLE

P1141 01迷宫

dongzhen @ 2024-08-25 19:42:15

是否应当开放一点空间(思考) 代码如下,调不出来

#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <string.h>
#define lnt long long
#define inf 0x7fffffff
using namespace std;
int xx;char ff,chh;inline int read(){
    xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}
    while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;
}
const int N=1e3+2;
struct point{
    int x,y;
    bool operator ==(point a){return a.x==x && a.y==y;}
    bool operator !=(point a){return !(*this==a);}
};
template<typename T>
#define tnt T
struct zy{
    tnt g[N][N];
    tnt &operator [](point a){return g[a.x][a.y];}
};
struct bcj{
    zy<point> g;zy<int> siz;
    bcj(){for(int i=0;i<N;++i){for(int e=0;e<N;++e){g[(point){i,e}]={i,e};}}}
    point find(point a){return g[a]==a? a: g[a]=find(g[a]);}
    void join(point a,point b){g[find(b)]=g[find(a)];}
}s;
zy<int> date;
int n,G;
void dfs(point);
int main(){
    n=read();G=read();
    for(int i=0;i<n;++i){
        for(int e=0;e<n;++e){
            char c=getchar();
            while(c!='0' && c!='1'){c=getchar();}
            date[{i,e}]=c-'0';
        }
    }
    for(int i=0;i<n;++i){
        for(int e=0;e<n;++e){
            if(!s.siz[{i,e}]){
                dfs({i,e});
            }
        }
    }
    while(G--){
        int x=read()-1,y=read()-1;
        point to=s.find({x,y});
        printf("%d\n",s.siz[s.find({x,y})]);
    }

    return 0;
}
bool is(point a){return (a.x!=n && a.y!=n && a.x!=-1 && a.y!=-1);}
void dfs(point x){
    s.siz[s.find(x)]++;
    if(s.find(x)!=x){s.siz[x]++;}
    point to={x.x+1,x.y};
    if(is(to) && !s.siz[to] && date[to]+date[x]==1){
        s.join(x,to);
        dfs(to);
    }
    to={x.x-1,x.y};
    if(is(to) && !s.siz[to] && date[to]+date[x]==1){
        s.join(x,to);
        dfs(to);
    }
    to={x.x,x.y-1};
    if(is(to) && !s.siz[to] && date[to]+date[x]==1){
        s.join(x,to);
        dfs(to);
    }
    to={x.x,x.y+1};
    if(is(to) && !s.siz[to] && date[to]+date[x]==1){
        s.join(x,to);
        dfs(to);
    }
}

|