BFS TLE求调【玄关】

small_moon @ 2024-07-28 15:23:36

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int read();
int n,m;
bool flag[N][N];
int dp[N][N];
int dx[5]={0,-1,1,0,0},
    dy[5]={0,0,0,-1,1};
char g[N][N];
struct Node{
    int x,y;
}q[N*N];
void bfs(int x,int y)
{
    bool vis[N][N]={};
    int head=1,tail=1;
    q[1]={x,y}; vis[x][y]=1;
    while(head<=tail)
    {
        Node k=q[head]; head++;
        for(int i=1;i<=4;i++)
        {
            int xx=k.x+dx[i],yy=k.y+dy[i];
            if(xx<=n && xx>0 && yy<=n && yy>0 && !vis[xx][yy] && g[xx][yy]!=g[k.x][k.y])
            {
                q[++tail]={xx,yy};
                vis[xx][yy]=1;
                flag[xx][yy]=1;
            }
        }
    }
    for(int i=1;i<=tail;i++)
        dp[q[i].x][q[i].y]=tail;
}
int main()
{
    n=read(); m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        if(!flag[x][y]) bfs(x,y);
        cout<<dp[x][y]<<endl;
    }
    return 0;
}
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

by LTTXiaochuan @ 2024-08-02 14:05:53

建议：

开个记忆数组lib用（用来记），把flag数组改成int型，再开个计数器ct，把flag存0/1变成存0/ct（ct是搜图的次数）

进数据以后先询问 flag[x][y] 是否是0，不是的话直接输出 lib[flag[x][y]] 然后 continue ，是0就搜图，然后在结尾输出ans的时候把ans存到lib[ct]里然后ct++即可

希望能够帮到你。

本人AC代码供参考：

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct poi{
    int x,y;
}que[N*N];
int xx[4]={0,1,0,-1};
int yy[4]={1,0,-1,0};
int mapk[N][N],book[N][N],lib[N*N],n,m;
int main()
{
    string s;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>s;
        for(int j=0; j<n; j++)
            mapk[i][j+1]=s[j]-'0';
    }
    int ct=1;
    for(int z=1; z<=m; z++)
    {
        int x,y,c,head=1,tail=2,ans=1;
        scanf("%d %d",&x,&y);
        if(book[x][y]!=0)
        {
            printf("%d\n",lib[book[x][y]]);
            continue;
        }
        book[x][y]=ct;
        que[1].x=x,que[1].y=y;
        while(head<tail)
        {
            c=mapk[que[head].x][que[head].y];
            for(int k=0; k<=3; k++)
            {
                int nx=que[head].x+xx[k];
                int ny=que[head].y+yy[k];
                if(nx<1 || nx>n || ny<1 || ny>n || book[nx][ny]==ct) continue;
                if(c+mapk[nx][ny]==1)
                {
                    book[nx][ny]=ct;
                    ans++;
                    que[tail].x=nx;
                    que[tail].y=ny;
                    tail++;
                }
            }
            head++;
        }
        lib[ct++]=ans;
        printf("%d\n",ans);
    }
    return 0;
}