24届暑期实习米哈游笔试题

���单选、多选和三道编程题。

下面是第一道编程题。

题目描述

米小游拿到了一个矩阵，矩阵上每一格有一个颜色，为红色（R）、绿色（G）和蓝色（B）这三种颜色的一种。然而米小游是蓝绿色盲，她无法分辨蓝色和绿色，所以在米小游眼里看来，这个矩阵只有两种颜色，因为蓝色和绿色在她眼里是一种颜色。

米小游会把相同颜色的部分看成是一个连通块。请注意，这里的连通块是上下左右四连通的。由于色盲的原因，米小游知道自己看到的连通块数量可能比真实的连通块数量少。你可以帮米小游计算连通块少了多少吗？

输入描述

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

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

输出描述

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

示例1

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

2 6

RRGGBB

RGBGRR

输出

3

说明

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

题解

#include 
using namespace std;
const int MAXN = 1005;
int n, m;
char color[MAXN][MAXN]; // 存储颜色信息
bool vis[MAXN][MAXN]; // 存储是否已访问
int dx[] = {0, 0, 1, -1}; // 四个方向
int dy[] = {1, -1, 0, 0};
int cnt; // 连通块数量
void dfs(int x, int y, char c) {
    vis[x][y] = true; // 标记为已访问
    for (int i = 0; i = n || ny = m) continue; // 越界判断
        if (!vis[nx][ny] && color[nx][ny] == c) dfs(nx, ny, c); // 没访问过且颜色相同
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i > color[i][j];
        }
    }
    int real_cnt = 0; // 真实的连通块数量
    for (int i = 0; i