华为OD刷题C卷 - 每日刷题31（园区参观路径，围棋的气）

1、（园区参观路径）：

这段代码是解决“园区参观路径”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，以及一个未使用的dfs方法，用于计算从园区起点到终点的不同参观路径数量。

main方法首先读取园区的长和宽，然后读取园区的布局信息，其中0表示可以参观，1表示不能参观。接着，调用getResult方法并打印出不同的路径数量。

getResult方法使用动态规划来解决这个问题。创建一个二维数组dp来存储到达每个位置的路径数量。通过遍历园区布局，如果当前位置可以参观，则更新dp数组，将到达该位置的路径数量设置为从上方和左方到达的路径数量之和。最后，返回到达终点的路径数量。

dfs方法是一个递归方法，用于深度优先搜索所有可能的路径。然而，此方法在问题规模较大时可能会超时，因为它没有利用动态规划来减少重复计算。

2、（围棋的气）：

这段代码是解决“围棋的气”的问题。它提供了一个Java类Main，其中包含main方法，用于计算围棋棋盘上黑棋和白棋的气的数量。

main方法首先读取黑棋和白棋的坐标，然后创建一个19x19的棋盘数组，将黑棋和白棋的位置分别标记为1和2。接着，使用一个二维数组offsets来表示可能的移动方向（上、下、左、右）。通过遍历棋盘上的每个空位（标记为0的位置），检查其周围是否有黑棋或白棋，从而确定每个空位是否是黑棋或白棋的气。

最后，打印出黑棋和白棋的气的数量。

package OD357;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @description 园区参观路径
 * @level 4
 * @score 200
 */

/**
 * 题目描述
 * 园区某部门举办了Family Day，邀请员工及其家属参加；
 * <p>
 * 将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角；
 * <p>
 * 家属参观园区时，只能向右和向下园区前进，求从起始园区到终点园区会有多少条不同的参观路径。
 * <p>
 * image
 * <p>
 * 输入描述
 * 第一行为园区的长和宽；
 * <p>
 * 后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观
 * <p>
 * 输出描述
 * 输出为不同的路径数量
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //dfs算法中最后结果
    static int res = 0;
    static int m;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //长 宽
        m = sc.nextInt();
        n = sc.nextInt();
        //园区
        int[][] park = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                park[i][j] = sc.nextInt();
            }
        }
        //输出有多少条不同的路径
        //dfs(0,0,park);
        long result = getResult(park);

        System.out.println(result);
    }

    //动态规划 返回从起点到终点的路径条数
    public static long getResult(int[][] park) {
        //起点和终点不能访问，则返回0
        if (park[0][0] == 1 || park[m - 1][n - 1] == 1) {
            return 0;
        }
        //dp[i][j]表示从起点到(i,j)点的路径条数  dp[i][j] = dp[i-1][j]+dp[i][j-1]
        long[][] dp = new long[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //遇到障碍，跳过
                if (park[i][j] == 1) continue;
                //只能向右和向下走 所以到达点(i,j)的上一步只能是从上或者从左边来
                if (i > 0) {
                    dp[i][j] += dp[i - 1][j];
                }
                if (j > 0) {
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 深度搜索 递归 能到达终点的个数 数量级大时会超时
     *
     * @param x
     * @param y
     * @param park
     * @return boolean
     * @create 2024/3/24 21:49
     */
    public static boolean dfs(int x, int y, int[][] park) {
        //如果园区起点和终点不能参观，直接false
        if (park[0][0] == 1 || park[m - 1][n - 1] == 1) {
            return false;
        }
        //返回标志
        if (x == park.length - 1 && y == park[0].length - 1) {
            return true;
        }
        //只能往右和往下走，不会重复
        //如果右边不为1 则往右走
        if (y + 1 < park[0].length && park[x][y + 1] != 1) {
            if (dfs(x, y + 1, park)) {
                res++;
            }
        }
        //如果下面不是1，则可以往下走
        if (x + 1 < park.length && park[x + 1][y] != 1) {
            if (dfs(x + 1, y, park)) {
                res++;
            }
        }
        //如果向下和向右都不能走
        return false;
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

package OD358;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @description 围棋的气
 * @level 4
 * @score 100
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //黑棋坐标
        int[] black = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //白棋坐标
        int[] white = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //棋盘
        int[][] board = new int[19][19];
        //取黑棋
        for (int i = 0; i < black.length; i += 2) {
            int x = black[i];
            int y = black[i + 1];
            //把该位置置为1
            board[x][y] = 1;
        }
        //取白棋
        for (int i = 0; i < white.length; i += 2) {
            int x = white[i];
            int y = white[i + 1];
            //把白棋置为2
            board[x][y] = 2;
        }
        //统计黑白棋的气
        int countBlack = 0;
        int countWhite = 0;
        //上下左右操作
        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        //遍历棋盘，寻找可能是黑白棋的气的点：该点为0，且上下左右存在1或者2
        for (int i = 0; i < 19; i++) {
            for (int j = 0; j < 19; j++) {
                if (board[i][j] == 0) {
                    //该点是否是黑棋的气
                    boolean isBlack = false;
                    boolean isWhite = false;
                    //遍历询问：该点是否是黑、白的气
                    for (int[] offset : offsets) {
                        int newI = i + offset[0];
                        int newJ = j + offset[1];
                        //如果下标越界，跳出
                        if (newI < 0 || newI >= 19 || newJ < 0 || newJ >= 19) continue;
                        isBlack = isBlack || board[newI][newJ] == 1;
                        isWhite = isWhite || board[newI][newJ] == 2;
                    }
                    //如果是黑棋的气，则黑棋气+1 因为是按顺序遍历的空白格，故同一个气只会被算作一次
                    if (isBlack) countBlack++;
                    if (isWhite) countWhite++;
                }
            }
        }
        System.out.println(countBlack + " " + countWhite);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64