70分，Tle求助！

Greeper @ 2024-10-09 23:01:02

#include<bits/stdc++.h>
using namespace std;
bool a[1005][1005];
bool f[1005][1005];
int n,m,ii,jj;
int gx[4]={0,1,0,-1},gy[4]={1,0,-1,0};
int bfs()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j]=0;
        }
    }
    int num=1;
    queue<int> x;
    queue<int> y;
    f[ii][jj]=1;
    x.push(ii);
    y.push(jj);
    while(!x.empty())
    {
        int nx=x.front(),ny=y.front();
        x.pop();y.pop();
        for(int i=0;i<4;i++)
        {
            int tx=nx+gx[i],ty=ny+gy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=n)
            {
                if(!f[tx][ty]&&a[nx][ny]!=a[tx][ty])
                {
                    f[tx][ty]=1;
                    num++;
                    x.push(tx);
                    y.push(ty);
                }
            }
        }
    }
    return num;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%1d",&a[i][j]);
        }
    }

    while(m--)
    {
        cin>>ii>>jj;
        cout<<bfs()<<endl;
    }
    return 0;
}

by hark @ 2024-10-12 20:43:29

我也是

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001;
char a[maxn][maxn];
const int fx[4]={-1,1,0,0};
const int fy[4]={0,0,-1,1};
int x,y,xx,yy;
bool f[maxn][maxn];
struct PRCS{
    int x;
    int y;
};
struct que{
    int r;
    int l;
    PRCS a[maxn*maxn];
    int size(){return r-l+1;}
    void push(int x,int y){r++;a[r].x=x;a[r].y=y;}
    int topx(){return a[l].x;}
    int topy(){return a[l].y;}
    void pop(){l++;}
    bool emgty(){
        if(r-l+1>0)return true;
        return false;
    }
    void clean(){l=1;r=0;}
}q;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    int ax,ay;
    int arr;
    while(m--){
        q.clean();
        arr=0;
        cin>>ax>>ay;
        q.push(ax,ay);
        f[ax][ay]=true;
        while(q.emgty()){
            x=q.topx();
            y=q.topy();
            q.pop();
            arr++;
            for(int k=0;k<4;k++){
                xx=x+fx[k];
                yy=y+fy[k];
                if(xx>0&&xx<=n && yy>0&&yy<=n && a[xx][yy]!=a[x][y] && f[xx][yy]==false){
                    f[xx][yy]=true;
                    q.push(xx,yy);
                }
            }
        }
        cout<<arr<<endl;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=false;
    }
    return 0;
}

by xiyu000 @ 2024-10-16 19:31:22

我也是

#include<bits/stdc++.h>
using namespace std;
bool vis[1005][1005];
char g[1005][1005]; 
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int ans = 0 ;
int n , m ;
void dfs(int x , int y){
    for(int i = 0 ; i < 4 ; i++){
        int nx = x + dx[i] , ny = y + dy[i] ;
        if(nx<1||nx>n||ny<1||ny>n)  continue;
        if(g[nx][ny]==g[x][y]||vis[nx][ny]) continue;
        ans++;
        vis[nx][ny]=1;
        dfs(nx,ny);
    }
}
int main(){
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            cin >> g[i][j];
        }
    }
    int x ;
    int y ;
    while(m--){
        memset(vis,0,sizeof(vis));
        cin >> x >> y ;
        ans = 0 ;
        vis[x][y]=1;
        dfs(x,y);
        cout << ans+1 << endl;
    }
    return 0 ;
}