一、题目

给定一个包含 0 和 1 的二维矩阵。给定一个初始位置和速度，
一个物体从给定的初始位置触发, 在给定的速度下进行移动, 遇到矩阵的边缘则发生镜面反射。无论物体经过 0 还是 1, 都不影响其速度。

请计算并给出经过 t 时间单位后, 物体经过 1 点的次数

矩阵以左上角位置为0, 0, 行(y)), 例如坐标[2, 1]表示第二列, 第一行。X 轴往右递增，Y 轴往下递增

1
2
3
4
5
6
7
8
9
10
 ±-----------------------> x递增
| 0 0 1 0 0 0 0 1 0 0 0 0
| 0 0 1 0 0 0 0 1 0 0 0 0
| 0 0 1 0 0 0 0 1 0 0 0 0
| 0 0 1 0 0 0 0 1 0 0 0 0
| 0 0 1 0 0 0 0 1 0 0 0 0
| 0 0 1 0 0 0 0 1 0 0 0 0
| 0 0 1 0 0 0 0 1 0 0 0 0
V
y递增

注意:

如果初始位置的点是 1, 也计算在内

时间的最小单位为1, 不考虑小于 1 个时间单位内经过的点

二、输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
第一行为初始信息
第二行开始一共h行, 为二维矩阵信息
其中
w, h为矩阵的宽和高
x, y为起始位置
sx, sy为初始速度
t为经过的时间
所有输入都是有效的, 数据范围如下
0 < w < 100
0 < h < 100
0 <= x < w
0 <= y < h
-1 <= sx <= 1
-1 <= sy <= 1
0 <= t < 100

三、输出

经过1的个数

四、示例

输入：

1
2
3
4
5
6
7
8
12 7 2 1 1 -1 13
001000010000
001000010000
001000010000
001000010000
001000010000
001000010000
001000010000

输出：
3

说明：初始位置为(2, 1), 速度为(1, -1), 那么13个时间单位后, 经过点1的个数为3

五、题解

  1. 输入坐标和表示的矩阵坐标是反着的，过程中需要处理否则会 index 越界异常
  2. 所谓镜面反射不用想dx，dy 到了每个边界怎么变化，只要到了边界 dx，dy 方向取反(取负数）即可。这个是核心。这个想明白了就是一道 easy 难度的题了

5.1 Java 实现

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
package org.stone.study.algo.ex202412;

import java.util.Scanner;
import java.util.stream.Stream;

public class ReflectAndCount {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] arr = sc.nextLine().split(" ");
        int[] nums = Stream.of(arr).mapToInt(Integer::parseInt).toArray();
        int m = nums[1];
        int n = nums[0];
        int[][] grid = new int[m][n];

        for(int i = 0; i < m; i++) {
            char[] chars = sc.nextLine().toCharArray();
            for(int j = 0; j < n; j++) {
                grid[i][j] = chars[j] - '0';
            }
        }

        int ans = countOne(grid, m, n, nums[2], nums[3], nums[4], nums[5], nums[6]);
        System.out.println(ans);
    }

    /**
     * 计算镜面反射后经过的 1 的个数
     * @param grid
     * @param m：行
     * @param n：列
     * @param x：列
     * @param y：行
     * @param dx：列的增量
     * @param dy：行的增量
     * @param t：时间线
     * @return
     */
    private static int countOne(int[][] grid, int m, int n, int x, int y, int dx, int dy, int t) {
        int ans = 0;
        while(t-- >= 0) {
            // 遇到 1 就计数, 注意起点 x 是列，y 是行
            if (grid[y][x] == 1) {
                ans++;
            }

            int x2 = x + dx, y2 = y + dy;
            if (x2 < 0 || x2 >= n) {
                dx = -dx;
            }
            if (y2 < 0 || y2 >= m) {
                dy = -dy;
            }

            x += dx;
            y += dy;
        }

        return ans;
    }
}

5.2 Python实现

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
def getOneCnt(matrix, w, h, x, y, sx, sy, t):

    res = 0
    while t >= 0:
        # 题目中的坐标和matrix的坐标是反着的，不处理会 index 越界
        if matrix[y][x] == 1:
            res += 1

        x2, y2 = x + sx, y + sy
        # 处理镜面反射
        if x2 < 0 or x2 >= w:
            sx = -sx

        if y2 < 0 or y2 >= h:
            sy = -sy

        x, y = x + sx, y + sy
        t -= 1
    return res


if __name__ == '__main__':
    w, h, x, y, sx, sy, t = map(int, input().split())
    matrix = [[int(c) for c in input()] for _ in range(h)]

    print(matrix)
    print(getOneCnt(matrix, w, h, x, y, sx, sy, t))