求助大佬!这道题究竟该怎么做?

题目描述
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

c++

2个回答

其实就是一个联通子图问题,如果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());
    }

}
qq_40946921
Italink 懂了,谢谢=.=
11 个月之前 回复
caozhy
贵阳老马马善福专门编写代码的老马就是我! 这个思路应该是对的。✔
11 个月之前 回复
qq_40946921
Italink 但是如果可以往回走的话,就不止7次了,它可以无限来回,所以我才借助visited这个数组来确保不往回走.
11 个月之前 回复

这是一个深度搜索算法的题目.有用的话请采纳=.=

#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;
}

图片说明

weixin_37893887
玄尺 深度搜索的有些问题
11 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!