ouyuchen12 @ 2024-12-10 19:12:18

#include<bits/stdc++.h>
using namespace std ;
char dfs[1005][1005];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int n , m , cnt ;
int vis[1005][1005] ;
bool check( int xx ,int yy )
{
    if( xx <= n && xx >= 1 && yy <= n && yy >= 1)
    {
        return 1 ;

    }
    return 0 ;
}
void chenlaoshi( int x , int y , int ww )
{
    for( int i = 0 ; i <= 3 ; i++ )
    {
        int xx = x + dx[i] ;
        int yy = y + dy[i] ;
        if( check(xx,yy))
        {
            if( vis[xx][yy] != ww )
            {
                if( dfs[xx][yy] == '1' && dfs[x][y] == '0' )
                {
                    vis[xx][yy] = ww ;
                    cnt++;
                    chenlaoshi(xx,yy,ww); 
                }
                else if( dfs[xx][yy] == '0' && dfs[x][y] == '1' )
                {
                    vis[xx][yy] = ww ;
                    cnt++;
                    chenlaoshi(xx,yy,ww);
                }
            }
        }
    }
    return ;
}
int main()
{
    cin >> n >> m ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        for( int j = 1 ; j <= n ; j++ )
        {
            cin >> dfs[i][j] ;
        }
    }
    for( int i = 1 ; i <= m ; i++ )
    {

        cnt = 1 ;
        int ex , ey ;
        cin >> ex >> ey ;
        vis[ex][ey] = i ;
        chenlaoshi(ex , ey , i ) ;
        cout << cnt << endl ;

    }                           
    return 0 ;
}

by chen_kun @ 2024-12-10 19:17:47

@ouyuchen12

又来一个暴搜的

这题数据很多，每次都带进去搜一遍肯定会TLE。

正解是先枚举整个矩阵，利用联通块的思想。因为在一个子矩阵中，所有格子能到的格子数量是一样的，所以另外开一个ans数组记录各个子矩阵每个元素能到达的格子数量，询问时直接输出就好了。

可能讲的不是很详细，你自己看我的代码理解一下

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,tx,ty,dx[5]={-1,1,0,0},dy[5]={0,0,-1,1},vis[1111][1111],ans,sum[1111],t=1,av[1111][1111];
char a[1111][1111];
struct node{
    int x,y;
};
void bfs(int x0,int y0){
    vis[x0][y0]=1;
    queue<node>q;
    q.push({x0,y0});
    ans=1;
    while(!q.empty()){
        x=q.front().x;
        y=q.front().y;
        q.pop();
        av[x][y]=t;
        for(int i=0;i<4;i++){
            tx=x+dx[i];
            ty=y+dy[i];
            if(a[x][y]!=a[tx][ty]&&vis[tx][ty]==0&&tx>=1&&tx<=n&&ty>=1&&ty<=n) vis[tx][ty]=1,q.push({tx,ty}),ans++;
        }
    }
}
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(vis[i][j]==0){
                bfs(i,j);
                sum[t]=ans;
                t++;
            }
        }
    }
    while(m--){
        cin>>x>>y;
        cout<<sum[av[x][y]]<<endl;
    }
    return 0;
}

by ouyuchen12 @ 2024-12-10 19:44:37

好的..

by CZX_HWH @ 2024-12-14 20:55:44

include<bits/stdc++.h>

using namespace std; const int N=1e3+5; int n,m,vis[N][N],cnt,s[N*N]; char mp[N][N]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; void DFS(int x,int y) { if(x<1||y<1||x>n||y>n) { return; } if(vis[x][y]>0) { return; } vis[x][y] = cnt,s[cnt]++; for(int i=0;i<4;i++) { if(mp[x][y]!=mp[x+dx[i]][y+dy[i]]) { DFS(x+dx[i],y+dy[i]); } } }

int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>mp[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(vis[i][j]==0) { cnt++,DFS(i,j); } } }

for(int i=1;i<=m;i++)
{
    int x,y;
    cin>>x>>y;
    cout<<s[vis[x][y]]<<endl;
}
return 0;

}

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,vis[N][N],cnt,s[N*N];
char mp[N][N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void DFS(int x,int y)
{
    if(x<1||y<1||x>n||y>n)
    {
        return;
    }
    if(vis[x][y]>0)
    {
        return;
    }
    vis[x][y] = cnt,s[cnt]++;
    for(int i=0;i<4;i++)
    {
        if(mp[x][y]!=mp[x+dx[i]][y+dy[i]])
        {
            DFS(x+dx[i],y+dy[i]);
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>mp[i][j];
        }
    }
    for(int  i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vis[i][j]==0) 
            {
                cnt++,DFS(i,j);
            }
        } 
    }

    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        cout<<s[vis[x][y]]<<endl;
    }
    return 0;
}

by ouyuchen12 @ 2024-12-20 18:26:17

@chen_kun AC了