hhhcj70分求调

P1141 01迷宫

__hjwucj__ @ 2023-12-22 22:04:32

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,smap[1001][1001],ans,c[1001][1001];
char a[1001][1001];
bool b[1001][1001];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0}/*,s*/;
void dfs (int x,int y)
{
    //cout<<x<<' '<<y<<' '<<s<<endl;
    ans++;
    b[x][y]=true;
    for (int i=0;i<4;i++)
    {
        int tx=x+dx[i],ty=y+dy[i];
        if (tx>0&&tx<=n&&ty>0&&ty<=n&&b[tx][ty]==false)
            if ((smap[x][y]==0&&smap[tx][ty]==1)||(smap[x][y]==1&&smap[tx][ty]==0))
                /*s++,*/dfs (tx,ty);
    }
}
signed main ()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cin>>a[i][j],smap[i][j]=a[i][j]-'0';
    for (int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        ans=0;
        memset (b,false,sizeof (b));
        b[x][y]=true;
        //s=0;
        if (c[x][y]==0) dfs (x,y);else 
            {
                cout<<c[x][y]<<endl;
                continue;
            }
        c[x][y]=ans;
        cout<<ans<<endl;
    }
    return 0;
}

|