C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 492K, 提交时间: 2020-03-21 22:39:18

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,ans1,ans2,vis[110][110],clo,nx,ny,qx[11000],qy[11000],he,ta;
char s[110][110];
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
void bfs(int sx,int sy){
    he=ta=1;
    qx[he]=sx;
    qy[he]=sy;
    while (he<=ta){
        fo(i,0,3){
            nx=qx[he]+dx[i];
            ny=qy[he]+dy[i];
            if (1<=nx&&nx<=n&&1<=ny&&ny<=n&&s[nx][ny]==s[sx][sy]&&vis[nx][ny]<clo){
                vis[nx][ny]=clo;
                qx[++ta]=nx;
                qy[ta]=ny;
            }
        }
        he++;
    }
}
int main(){
    scanf("%d",&n);
    fo(i,1,n) scanf("%s",s[i]+1);
    clo=1;
    fo(sx,1,n)
        fo(sy,1,n)
            if (vis[sx][sy]<clo){
                vis[sx][sy]=clo;
                ans1++;
                bfs(sx,sy);
            }
    fo(i,1,n)
        fo(j,1,n)
            if (s[i][j]=='G') s[i][j]='R';
    clo++;
    fo(sx,1,n)
        fo(sy,1,n)
            if (vis[sx][sy]<clo){
                vis[sx][sy]=clo;
                ans2++;
                bfs(sx,sy);
            }
    printf("%d %d\n",ans1,ans2);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 4580K, 提交时间: 2020-04-05 22:08:09

#include<iostream>
#include<cstring>
using namespace std;
char mp[1000][1000],str;
int vis[1000][1000],to[4][2]={0,-1,0,1,-1,0,1,0},n;
void dfs(int x,int y){
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+to[i][0];
        int yy=y+to[i][1];
        if(xx>=0&&yy>=0&&xx<n&&yy<n&&!vis[xx][yy]&&mp[xx][yy]==str){
            dfs(xx,yy);
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mp[i][j];
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            str=mp[i][j];
            if(!vis[i][j]){
                dfs(i,j);
                ans++;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(mp[i][j]=='G')
            mp[i][j]='R';
        }
    }
    memset(vis,0,sizeof(vis));
    int ans1=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            str=mp[i][j];
            if(!vis[i][j]){
                dfs(i,j);
                ans1++;
            }
        }
    }
    cout<<ans<<" "<<ans1<<endl;
    return 0;
}