bfs爆0求助（玄关）

ycy1124 @ 2024-05-05 12:39:45

#include<bits/stdc++.h>
using namespace std;
char a[2001][2001];
bool vis[2001][2001];
queue <int> x,y;
int p1[4]={1,-1,0,0},p2[4]={0,0,1,-1};
int n,m;
void bfs(int x1,int y1)
{
    vis[x1][y1]=1;
    for(int i=0;i<=3;i++)
    {
        if(x1+p1[i]>0&&x1+p1[i]<=n&&y1+p2[i]>0&&y1+p2[i]<=n&&!vis[x1+p1[i]][y1+p2[i]])
        {
            if(a[x1+p1[i]][y1+p2[i]]!=a[x1][y1])
            {
                x.push(x1+p1[i]);
                y.push(y1+p2[i]);
            }
         } 
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=getchar();
        }
        getchar();
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                vis[j][k]=0;
            }
        }
        int x1,y1;
        cin>>x1>>y1;
        x.push(x1);
        y.push(y1);
        int js=0;
        while(!x.empty())
        {
            js++;
            bfs(x.front(),y.front());
            x.pop();
            y.pop();
        }
        cout<<js<<'\n';
    }
    return 0;
}

by DevilsFlame @ 2024-05-05 12:47:38

        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                vis[j][k]=0;
            }
        }

这里可以用memset 最主要的：询问从某一格开始能移动到多少个格子 （包含自身）

by DevilsFlame @ 2024-05-05 12:53:01

询问从某一格开始能移动到多少个格子 （包含自身）
这当我没说

by DevilsFlame @ 2024-05-05 13:02:47

判断有一点问题，具体如下：

#include<bits/stdc++.h>
using namespace std;
char a[2001][2001];
bool vis[2001][2001];
queue <int> x,y;
int p1[4]={1,-1,0,0},p2[4]={0,0,1,-1};
int n,m;
void bfs(int x1,int y1)
{

    for(int i=0;i<=3;i++)
    {
        if(x1+p1[i]>0&&x1+p1[i]<=n&&y1+p2[i]>0&&y1+p2[i]<=n&&!vis[x1+p1[i]][y1+p2[i]])
        {
            if(a[x1+p1[i]][y1+p2[i]]!=a[x1][y1])
            {
                x.push(x1+p1[i]);
                y.push(y1+p2[i]);
                vis[x1 + p1[i]][y1+p2[i]]=1;//就这里
            }
         }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
//          a[i][j]=getchar();
            cin >> a[i][j];
        }
//      getchar();
    }
    for(int i=1;i<=m;i++)
    {
        memset(vis,0,sizeof(vis));
        int x1,y1;
        cin>>x1>>y1;
        vis[x1][y1]=1;
        x.push(x1);
        y.push(y1);
        int js=0;
        while(!x.empty())
        {
            js++;
            bfs(x.front(),y.front());
//          cout << x.front() <<' '<<y.front()<<endl;
            x.pop();
            y.pop();
        }
        cout<<js<<'\n';
    }
    return 0;
}

by DevilsFlame @ 2024-05-05 13:02:59

反正TLE

by ycy1124 @ 2024-05-05 13:13:27

@yhdxg

谢谢大佬，一关