40分求助

HOG_ksc @ 2024-07-06 09:49:45

#include<bits/stdc++.h>
using namespace std;
long long s,n,m,x,y;
bool labyrinth[1145][1145],qc[1145][1145];
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
string a;
struct point
{
    long long x,y;
}now,temp;
queue<point> r;
long long startx,starty;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        for(int j=1;j<=n;j++) labyrinth[i][j]=a[j-1]-'0';
    }
    while(m--)
    {
        cin>>startx>>starty;
        now.x=startx,now.y=starty;
        r.push(now);
        s=0;
        while(!r.empty())
        {
            x=r.front().x;
            y=r.front().y;
            for(int i=0;i<4;i++)
            {
                int tx=x+dx[i],ty=y+dy[i];
                if(tx<1||tx>n||ty<1||ty>n) continue;
                if(labyrinth[tx][ty]==labyrinth[x][y]) continue;
                if(qc[tx][ty]) continue;
                qc[tx][ty]=1;
                temp.x=tx,temp.y=ty;
                r.push(temp);
                s++;
            }
            r.pop();
        }
        cout<<s<<endl;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) qc[i][j]=0;
    }
 } 

by lijunda @ 2024-07-06 10:16:25

@HOG_ksc ```cpp

#include<bits/stdc++.h>
using namespace std;
int n,m,tot=0,val=-1;
const int N=1e3+10;
char b[N][N];
int a[N][N];
int cnt[N*N]; 
queue <int> xx;
queue <int> yy;
int f[]={0,0,0,1,-1};
int w[]={0,1,-1,0,0};
int r[N][N]; 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>b[i][j],a[i][j]=b[i][j]-'0';
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(r[i][j]<0) continue;
            int ans=1;
            r[i][j]=val;
            xx.push(i);
            yy.push(j);
            while(xx.size()!=0)
            {
                for(int k=1;k<=4;k++)
                {
                    if(xx.front()+f[k]<=n&&xx.front()+f[k]>=1&&yy.front()+w[k]<=n&&yy.front()+w[k]>=1&&r[xx.front()+f[k]][yy.front()+w[k]]>=0&&r[xx.front()+f[k]][yy.front()+w[k]]!=val&&a[xx.front()+f[k]][yy.front()+w[k]]==!a[xx.front()][yy.front()])
                    {
                        xx.push(xx.front()+f[k]),yy.push(yy.front()+w[k]);
                        r[xx.front()+f[k]][yy.front()+w[k]]=val,ans++;
                    }   
                }   
                xx.pop(),yy.pop();
            }
            cnt[tot]=ans,tot++,val--;
        }   
    } 
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<abs(cnt[abs(r[x][y])-1])<<endl;
    }
}