。。。

IAKIOI66666 @ 2024-07-29 14:14:28

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct node{
    int x,y;
};
queue<node> q;
int n,m,x,y,a[1050][1050];
string s;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        for(int j=0;j<n;j++)
            a[i][j+1]=s[i]-'0';
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        int z=a[x][y],ans=0;
        q.push({x,y});
        while(!q.empty())
        {
            node b=q.front();
            for(int i=0;i<=3;i++)
            {
                int x1=b.x+xx[i],y1=b.y+yy[i];
                if(x1<1||y1<1||x1>n||y1>n||z==a[x1][y1]||a[x1][y1]==2)continue;
                a[x1][y1]=2,q.push({x1,y1});ans++;
            }
            q.pop();
        }
        cout<<ans+1<<endl;
    } 
    return 0;
}

by 潘德理2010 @ 2024-07-29 14:23:04

你的标题应该写成“求调”之类的内容，而不是三个句号。这是不符合讨论区规则的。如果你要进行补充说明的话可以在帖子里面说。

另外，你好好看看你的代码的时间复杂度，以及本题数据范围。你这个代码会超时的。

另外你下面那个循环怎么里外都是 i？

by 潘德理2010 @ 2024-07-29 14:23:13

@IAKIOI66666

by xiangby @ 2024-08-03 21:15:26

@IAKIOI66666 你写的是一个纯的BFS，但出现了如下问题

1.内外层的变量名一样

2.对于当前格子的0/1数据没有实时更新

3. a[i][j+1]=s[i]-'0';//s[i]???

4. 你的a数组每次计算完无法复原。应该开一个vis数组

5.你的纯DFS会超时，所以要进行优化，所以我们知道:同一个起点的路径上的每个点的答案相同所以这里直接使用i做标记anss[i]表示i号路径上的点的答案。

6.还有很多其他问题我在代码中都标注了

所以一下就是ac代码：（仅供参考！！）

//#include<iostream>
//#include<queue>
//#include<cstring>
#include<bits/stdc++.h> 
using namespace std;
struct node{
    int x,y;
};
queue<node> q;
int n,m,x,y,a[1050][1050],vis[1050][1050],anss[1000050];
string s;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        for(int j=0;j<n;j++){
            a[i][j+1]=s[j]-'0';//s[i]???
        }
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        if(anss[vis[x][y]]){
            cout<<anss[vis[x][y]]<<'\n';
            continue;
        } 
        vis[x][y]=i;
        anss[i]=1; 
        /*
        这里要先把起点标记好。
        这里加一是为了记忆时不会因为没有路径值为零反复搜索.
        */ 
        int z=a[x][y],ans=0;
        q.push({x,y});
        node bb=q.front();
        while(!q.empty())
        {
            node b=q.front();
            for(int j=0;j<=3;j++)//内外层的变量名一样
            {
                z=a[b.x][b.y];//对于当前格子的01数据要实时更新 
                int x1=b.x+xx[j],y1=b.y+yy[j];
                if(x1<1||y1<1||x1>n||y1>n||z==a[x1][y1]||vis[x1][y1])continue;
                vis[x1][y1]=i;
                /*
                同一个起点的路径上的每个点的答案相同所以这里直接使用i做标记anss[i]表示i号路径上的点的答案。
                */
                q.push({x1,y1});
                anss[i]++;
            }
            q.pop();
        }
        cout<<anss[i]<<endl;
    } 
    return 0;
}

by IAKIOI66666 @ 2024-08-03 21:19:55

@xiangby 谢谢大佬