wangborui123 @ 2023-12-23 10:59:51

#include <bits/stdc++.h>
using namespace std;
char a[2005][2005];
struct h
{
    int x,y;
};
int z[5][5]={{1,0},{-1,0},{0,1},{0,-1}};
queue<h>q;
bool f[2005][2005];
int main()
{
    int ans=0;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int t=0;t<m;t++)
    {
        int u,v;
        cin>>u>>v;
        q.push((h){u,v});
        while(!q.empty())
        {
            h now=q.front();
            int ux=now.x,uy=now.y;
            q.pop();
            if(ux<1 or ux>n or uy<1 or uy>n or f[ux][uy]==1)
            {
                continue;
            }
            f[ux][uy]=1;
            ans++;
            for(int i=0;i<4;i++)
            {
                if(a[ux+z[i][0]][uy+z[i][1]]!=a[ux][uy])q.push((h){ux+z[i][0],uy+z[i][1]});
            }
        }
        memset(f,0,sizeof(f));//知道问题在这里但是不会优化了，求调
        cout<<ans<<endl;
        ans=0;
    }
    return 0;
}

}

by kyEEcccccc @ 2023-12-23 11:13:29

拿个vector把用到的位置全部存起来，然后清空的时候把这些位置拿出来清空即可。

by wangborui123 @ 2023-12-23 13:59:32

@kyEEcccccc OK，我去试试，谢谢大佬

by wangborui123 @ 2023-12-23 14:06:20

@kyEEcccccc 80了，但还有两个TLE

by wangborui123 @ 2023-12-23 14:06:41

@kyEEcccccc

#include <bits/stdc++.h>
using namespace std;
char a[2005][2005];
struct h
{
    int x,y;
};
int z[5][5]={{1,0},{-1,0},{0,1},{0,-1}};
queue<h>q;
bool f[2005][2005];
int main()
{
    int ans=0;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int t=0;t<m;t++)
    {
        vector<h>xx;
        int u,v;
        cin>>u>>v;
        q.push((h){u,v});
        while(!q.empty())
        {
            h now=q.front();
            int ux=now.x,uy=now.y;
            q.pop();
            if(ux<1 or ux>n or uy<1 or uy>n or f[ux][uy]==1)
            {
                continue;
            }
            f[ux][uy]=1;
            xx.push_back((h){ux,uy});
            ans++;
            for(int i=0;i<4;i++)
            {
                if(a[ux+z[i][0]][uy+z[i][1]]!=a[ux][uy])q.push((h){ux+z[i][0],uy+z[i][1]});
            }
        }
        for(int i=0;i<xx.size();i++)
        {
            h node=xx[i];
            int x1=node.x,y1=node.y;
            f[x1][y1]=0;
        }
        cout<<ans<<endl;
        ans=0;
    }
    return 0;
}

by kyEEcccccc @ 2023-12-23 14:32:15

vector开在外面试试。我不太懂，可能复杂度不对？

by wangborui123 @ 2023-12-23 14:38:00

@kyEEcccccc 我现在应该是o(n^2)了吧，vector如果开在外面那我又要清空vector了啊，所以我放到循环里面了

by kyEEcccccc @ 2023-12-23 18:14:51

清空vector的复杂度是vector的长度。创建/析构一个vector的时间同样如此。但是vector是动态空间，一个已经存放过若干元素的vector，clear以后重新加入元素的时间和一个新vector加入相同数量的元素，前者可能快很多。在总操作次数多时尤其如此。