题目思路

朴素的求连通块个数。两遍dfs，一次正常算，一次把B,G看作一样的字符算。做差即可。

代码

C++

#include<iostream>

using namespace std;

int n, m;
string s[1010];
bool vis1[1010][1010], vis2[1010][1010];
const int mv[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int dfs1(int x, int y) {
	if(x < 0 || x >= n) return 0;
	if(y < 0 || y >= m) return 0;
	if(vis1[x][y]) return 0;
	if(!vis1[x][y]) vis1[x][y] = true;
	for(int i = 0; i < 4; i++) {
		if(x + mv[i][0] < 0 || x + mv[i][0] >= n) continue;
		if(y + mv[i][1] < 0 || y + mv[i][1] >= m) continue;
		if(s[x + mv[i][0]][y + mv[i][1]] == s[x][y])
			dfs1(x + mv[i][0], y + mv[i][1]);
	}
	return 1;
}
int dfs2(int x, int y) {
	if(x < 0 || x >= n) return 0;
	if(y < 0 || y >= m) return 0;
	if(vis2[x][y]) return 0;
	if(!vis2[x][y]) vis2[x][y] = true;
	for(int i = 0; i < 4; i++) {
		if(x + mv[i][0] < 0 || x + mv[i][0] >= n) continue;
		if(y + mv[i][1] < 0 || y + mv[i][1] >= m) continue;
		if(s[x][y] == 'G' || s[x][y] == 'B') {
			if(s[x + mv[i][0]][y + mv[i][1]] == 'G' || s[x + mv[i][0]][y + mv[i][1]] == 'B')
				dfs2(x + mv[i][0], y + mv[i][1]);
		}
		else if(s[x + mv[i][0]][y + mv[i][1]] == s[x][y])
			dfs2(x + mv[i][0], y + mv[i][1]);
	}
	return 1;
}
int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> s[i];
	}
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cnt += dfs1(i, j);
		}
	}
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cnt -= dfs2(i, j);
		}
	}
	
	cout << cnt;
	return 0;
}

Java

import java.util.*;

public class Main {
    static final int N = 1010;
    static char[][] g = new char[N][N];
    static boolean[][] st = new boolean[N][N];
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};
    static int n, m;
    static int[] res = new int[2];

    static void dfs(int x, int y, char c) {
        st[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b] || g[a][b] != c) continue;
            dfs(a, b, c);
        }
    }

    static void query(int u) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!st[i][j]) {
                    dfs(i, j, g[i][j]);
                    cnt++;
                }
            }
        }
        res[u]=cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; i++) {
            g[i] = sc.next().toCharArray();
        }
        query(0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'B') g[i][j] = 'G';
            }
        }
        for (int i = 0; i < n; i++) Arrays.fill(st[i], false);
        query(1);
        System.out.println(res[0] - res[1]);
    }
}

Python3（必须要使用pypy才可以ac）

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().strip().split())
arr = [input().strip() for _ in range(n)]

visited1 = [[False] * m for _ in range(n)]
visited2 = [[False] * m for _ in range(n)]

def dfs(arr, visited1, i, j):
    visited1[i][j] = True
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    for x, y in direction:
        si = i + x
        sj = j + y
        if si >= 0 and si < n and sj >= 0 and sj < m and not visited1[si][sj] and arr[i][j] == arr[si][sj]:
            dfs(arr, visited1, si, sj)

def dfs2(arr, visited2, i, j):
    visited2[i][j] = True
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    for x, y in direction:
        si = i + x
        sj = j + y
        if si >= 0 and si < n and sj >= 0 and sj < m and not visited2[si][sj]:
            if arr[i][j] == 'G' or arr[i][j] == 'B':
                if arr[si][sj] == 'G' or arr[si][sj] == 'B':
                    dfs2(arr,visited2, si, sj)
            elif arr[i][j] == arr[si][sj]:
                dfs2(arr, visited2, si, sj)


    
count = 0
for i in range(n):
    for j in range(m):
        if not visited1[i][j]:
            dfs(arr, visited1, i, j)
            count += 1

for i in range(n):
    for j in range(m):
        if not visited2[i][j]:
            dfs2(arr, visited2, i, j)
            count -= 1


print(count)

题目内容

米小游是一位蓝绿色盲，他面对许多日常生活中我们认为很容易的事情，都需要付出比常人更大的努力。

有一天，他收到了一个矩阵，矩阵的每个格子的颜色是红色、绿色和蓝色三种颜色之中的一个，但由于他无法分辨蓝色和绿色，因此在他眼里这个矩阵只有两种颜色。他想要对这个矩阵进行分析，但是由于他的视觉缺陷，他自己看到的连通块数量可能比实际的连通块数量少。

你可以帮米小游计算连通块少了多少吗？

注意： 题目中的连通是指上下左右的四连通。

输入描述

第一行输入两个正整数 $n$ 和 $m$ ，代表矩阵的行数和列数。

接下来的 $n$ 行，每行输入一个长度为 $m$ 的，仅包含 R 、G 、B 三种颜色的字符串，代表米小游拿到的矩阵。

$1\le n,m\le 1000$

输出描述

一个整数，代表米小游视角里比真实情况少的连通块数量。

样例

输入

2 6
RRGGBB
RGBGRR

输出

3

样例解释

米小游视角里有 $3$ 个连通块，而实际上有 $6$ 个连通块，所以米小游视角的连通块数量比真实情况少了 $3$ 个。