求助大佬！这道题究竟该怎么做？
题目描述
2021年，九月，小w发现自己位于一个巨大的由黑格和白格组成的nn行mm列的迷宫中。
小w只能从白格走到黑格或从黑格走到白格，
小w找到了ljf，她想知道自己从每一个格子出发可以走到多少个格子。
但是ljf忙于在ioi中虐场，把问题留给了你。
输入格式
第一行：两个整数 n,mn,m
接下来nn行mm列描述这个迷宫
若第ii行，第jj个为1，则表示迷宫的第ii行第jj个格子为黑，反之则为白。
输出格式
nn行mm列
第ii行第jj个数表示从第ii行第jj个格子能走到的格子总数
输入样例
1 2
10
输出样例
2 2
数据范围
对于30%的数据 n,m≤50n,m≤50
另外10%的数据 所有格子都为黑格
对于100%的数据 n,m≤2000n,m≤2000
这是一个深度搜索算法的题目.有用的话请采纳=.=
#include<iostream>
using namespace std;
#define M 2000
int graph[M][M] = {1,0};
int result[M][M];
int visited[M][M];
int nx, ny,n=1,m=2;
int dx[4] = { 1,-1,0,0 },
dy[4] = { 0,0,1,-1 };
int max=0;
int search(int x,int y,int k) { //深度优先搜索算法
visited[x][y] = 1;
max = k > max ? k : max;
for (int i = 0; i < 4; i++) { //四个方向进行搜索
nx = x + dx[i];
ny = y + dy[i];
if (nx >= 0 && nx < n&&ny >= 0 && ny < m && !visited[nx][ny] && graph[x][y] != graph[nx][ny]) { //探测判断
visited[nx][ny] = 1;
search(nx, ny, k+1); //进行下一次探测
}
}
return max;
}
int main(){
cin >> n >> m;
for (int i=0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
memset(visited, 0, sizeof(visited)); //数据初始化
max = 0;
result[i][j] = search(i, j, 1);
}
}
cout << "结果：" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
return 0;
}
其实就是一个联通子图问题，如果A可以走到B，那么B也可以走到A，如果输入
1 0 0 0
0 1 0 1
那么输出应该是：
7 7 1 7
7 7 7 7
所以qq_40946921的回答是不对的。
/**
* 连通图
*
* @author yufei.liu
*/
public class Application {
private static final int BASE = 1000000;
/**
* 生成一个矩阵
*
* @return 矩阵
*/
private static int[][] createMaze1() {
return new int[][]{
{1, 0, 0, 0},
{0, 1, 0, 1}
};
}
/**
* 生成一个矩阵
*
* @return 矩阵
*/
private static int[][] createMaze2() {
return new int[][]{
{1, 1, 0, 0},
{0, 1, 0, 1}
};
}
/**
* 从(m, n)进行染色
* 染色0 -> -2, 1 -> -1
*
* @param maze 矩阵
* @param m 开始染色的位置，0开始
* @param n 开始染色的位置，0开始
* @return 矩阵
*/
private static int[][] color(int[][] maze, int m, int n) {
if (maze[m][n] < 0) {
return maze;
}
// 开始染色
maze[m][n] = maze[m][n] == 0 ? -2 : -1;
if (m != 0) {
if (judge(maze[m][n], maze[m - 1][n]) < 0) {
color(maze, m - 1, n);
}
}
if (n != 0) {
if (judge(maze[m][n], maze[m][n - 1]) < 0) {
color(maze, m, n - 1);
}
}
if (m != maze.length - 1) {
if (judge(maze[m][n], maze[m + 1][n]) < 0) {
color(maze, m + 1, n);
}
}
if (n != maze[0].length - 1) {
if (judge(maze[m][n], maze[m][n + 1]) < 0) {
color(maze, m, n + 1);
}
}
return maze;
}
/**
* 如果ab是不同颜色，返回b对应的染色值
* 如果ab是相同颜色，返回b
*/
private static int judge(int a, int b) {
if (b != 0 && b != 1) {
return b;
}
a = a == -1 ? 1 : 0;
if (a != b) {
return b == 0 ? -2 : -1;
}
return b;
}
/**
* 将联通集连接起来
*
* @param maze 矩阵
* @return 这一次连通图的结点数量
*/
private static int color(int[][] maze) {
int count = 0;
int m = maze.length;
int n = maze[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maze[i][j] < 0) {
count++;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maze[i][j] < 0) {
maze[i][j] = count + BASE;
}
}
}
return count;
}
/**
* 打印矩阵
*
* @param maze maze
*/
private static void print(int[][] maze, int base) {
int m = maze.length;
int n = maze[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(maze[i][j] - base + "\t");
}
System.out.println();
}
System.out.println("\n\n");
}
private static void handler(int[][] maze) {
int m = maze.length;
int n = maze[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maze[i][j] == 0 || maze[i][j] == 1) {
color(maze, i, j);
color(maze);
}
}
}
print(maze, BASE);
}
public static void main(String[] args) {
handler(createMaze1());
handler(createMaze2());
}
}