蒟蒻WE求调

Samsd @ 2024-08-23 12:42:58

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,x,y,ans[1005][1005];
bool vis[1005][1005];
char a[1005][1005];
const int fx[]={0,0,1,-1},fy[]={1,-1,0,0};
struct node
{
    int x,y;
};
queue<node>q;
int bfs(int sx,int sy)
{
    int cnt=1;
    memset(vis,0,sizeof vis);
    vis[sx][sy]=1;
    q.push((node){sx,sy});
    while(!q.empty())
    {
        node p=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int xx=p.x+fx[i],yy=p.y+fy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!=a[p.x][p.y])
            {
                q.push((node){xx,yy});
                vis[xx][yy]=1;
                cnt++;
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(vis[i][j])ans[i][j]=cnt;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(ans[i][j]==0)bfs(i,j);
    for(int k=1;k<=m;k++)
    {
        cin>>x>>y;
        cout<<ans[x][y]<<'\n';
    }
    return 0;
}

by hhztl @ 2024-08-23 12:51:52

@Samsd 可能是因为你的bfs函数没有返回值

by Gcc_Gdb_7_8_1 @ 2024-08-23 12:55:08

@Samsd 在bfs的最后一行加上return 0;或者把int bfs(int sx,int sy)改成void bfs(int sx,int sy)

by Gcc_Gdb_7_8_1 @ 2024-08-23 12:58:20

还有不用把所有的点的ans都算出来，问到哪个点就算哪个(带记忆化)

by Qinglan2011 @ 2024-08-23 12:58:26

@Samsd 泥的返回值呢？

by Qinglan2011 @ 2024-08-23 13:00:25

@Samsd 泥的点怎么都在算？

by Gcc_Gdb_7_8_1 @ 2024-08-23 13:04:29

光加上return 0;不够，因为会TLE

by Gcc_Gdb_7_8_1 @ 2024-08-23 13:13:01

这是 90 pts 的 Code:

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,x,y,ans[1005][1005];
bool vis[1005][1005];
char a[1005][1005];
const int fx[]={0,0,1,-1},fy[]={1,-1,0,0};
struct node
{
    int x,y;
} need[1000005];
queue<node>q;
void bfs(int sx,int sy)
{
    int cnt=1, tot=0;
    memset(vis,0,sizeof vis);
    vis[sx][sy]=1;
    need[++tot] = ((node){sx,sy});
    q.push((node){sx,sy});
    while(!q.empty())
    {
        node p=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int xx=p.x+fx[i],yy=p.y+fy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!=a[p.x][p.y])
            {
                q.push((node){xx,yy});
                vis[xx][yy]=1;
                need[++tot] = ((node){xx,yy});
                cnt++;
            }
        }
    }
    for (int i = 1; i <= tot; ++i) {
        ans[need[i].x][need[i].y] = cnt;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int k=1;k<=m;k++)
    {
        cin>>x>>y;
        if(ans[x][y]==0)bfs(x,y);
        cout<<ans[x][y]<<'\n';
    }
    return 0;
}

TLE on Subtask#1:#2

by Gcc_Gdb_7_8_1 @ 2024-08-23 13:14:32

@Samsd 我正在调试,你先看看

by Samsd @ 2024-08-23 19:39:49

@所有人 谢谢分析

by Samsd @ 2024-08-23 19:41:15

@Gcc_Gdb_7_8_1 谢谢代码