米哈游2023.3.19后端笔试第一题：米小游的色盲视角

米小游拿到了一个矩阵，矩阵上每一格有一个颜色，为红色(R)、绿色(G)和蓝色(B)这三种颜色的一种。然而米小游是蓝绿色盲，她无法分辨蓝色和绿色，所以在米小游眼里看来，这个矩阵只有两种颜色，因为蓝色和绿色在她眼里是一种颜色。米小游会把相同颜色的部分看成是一个连通块。请注意，这里的连通块是上下左右四连通的。由于色盲的原因，米小游知道自己看到的连通块数量可能比真实的连通块数量少。你可以帮米小游计算连通块少了多少吗？

输入描述：输入描述第一行输入两个正整数n和m，代表矩阵的行数和列数。接下来的n行，每行输入一个长度为m的、仅包含' R '、' G '、’B '三种颜色的字符串。代表米小游拿到的矩阵。1<=n，<=1000。

思路：递归，将上下左右相同的颜色块找出来标记为0，代码：

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int m = sc.nextInt();

sc.nextLine();

StringBuilder strs = new StringBuilder("");

while (sc.hasNext()){

strs.append(sc.nextLine());

}

String str = new String(strs);

int[][] number = new int[n][m];

int[][] numberF = new int[n][m];

int nn = 0;

for(int i = 0; i < n; i++){

for(int j = 0; j < m; j++){

char temp = str.charAt(nn);

if (temp == 'R'){

number[i][j] = 1;

numberF[i][j] = 1;

}else if (temp == 'G'){

number[i][j] = 2;

numberF[i][j] = 2;

}else{

number[i][j] = 3;

numberF[i][j] = 2;

}

nn++;

}

}

int truth= 0;

for (int i = 0; i < n; i++){

for (int j = 0; j < m; j++){

if (number[i][j] == 0){

continue;

}else{

truth++;

solve(number, i, j, n, m, number[i][j]);

}

}

}

int fake = 0;

for (int i = 0; i < n; i++){

for (int j = 0; j < m; j++){

if (numberF[i][j] == 0){

continue;

}else{

fake++;

solve(numberF, i, j, n, m, numberF[i][j]);

}

}

}

System.out.println(truth - fake);

}

public static void solve(int[][] number, int i, int j, int n, int m, int color){

        number[i][j] = 0;

        //上：

        if (i - 1 >= 0){

            if (number[i - 1][j] == color){

                solve(number, i - 1, j, n, m, color);

            }

        }

        //下：

        if (i + 1 < n){

            if (number[i + 1][j] == color){

                solve(number, i + 1, j, n, m, color);

            }

        }

        //左：

        if (j - 1 >= 0){

            if (number[i][j - 1] == color){

                solve(number, i, j - 1, n, m, color);

            }

        }

        //右：

        if (j + 1 < m){

            if (number[i][j + 1] == color){

                solve(number, i, j + 1, n, m, color);

            }

        }

        return;

    }

}