【2025刷题笔记】- 反射计数
刷题笔记合集🔗
反射计数
问题描述
给定一个包含 0 和 1 的二维矩阵。
给定一个初始位置和速度，一个物体从给定的初始位置出发，在给定的速度下进行移动，遇到矩阵的边缘则发生镜面反射。
无论物体经过 0 还是 1，都不影响其速度。
请计算并给出经过 时间单位后，物体经过 1 点的次数。
矩阵以左上角位置为 （列(
)，行(
)），例如下面 A 点坐标为
（第二列，第一行）
注意：
- 如果初始位置的点是 1，也计算在内
- 时间的最小单位为 1，不考虑小于 1 个时间单位内经过的点
输入格式
第一行为初始信息，包含七个整数 、
、
、
、
、
、
，分别表示：
，
为矩阵的宽和高
，
为起始位置
，
为初始速度
为经过的时间
第二行开始一共 行，为二维矩阵信息，每行包含
个字符，只有 0 和 1。
输出格式
输出一个整数，表示经过 1 的个数。
注意初始位置也要计算在内。
样例输入
12 7 2 1 1 -1 13
001000010000
001000010000
001000010000
001000010000
001000010000
001000010000
001000010000
样例输出
3
数据范围
| 样例 | 解释说明 |
|---|---|
| 样例1 | 初始位置为（2,1），速度为（1,-1），那么13个时间单位后，经过点1的个数为3 |
题解
这道题目模拟了一个物体在二维矩阵中移动的过程，要求统计它经过值为1的格子的次数。
主要难点在于处理边界反射的逻辑。当物体到达矩阵边界时，需要按照镜面反射的规则改变其速度方向并计算新的位置。
解题思路：
- 首先解析输入，获取矩阵尺寸、初始位置、初始速度和时间。
- 然后，模拟物体在t个时间单位内的移动过程：
- 从初始位置开始，检查该位置的值是否为1
- 根据当前速度计算下一个位置
- 检查是否碰到边界，如果是，应用反射规则并调整速度
- 移动到新位置，时间减一
- 重复上述过程直到时间结束
关于边界反射的处理：
- 当x < 0时，x应该变为1，sx变为-sx（向左碰到边界后向右反弹）
- 当x >= w时，x应该变为w-2，sx变为-sx（向右碰到边界后向左反弹）
- 当y < 0时，y应该变为1，sy变为-sy（向上碰到边界后向下反弹）
- 当y >= h时，y应该变为h-2，sy变为-sy（向下碰到边界后向上反弹）
需要注意的是，本题中(x,y)坐标表示矩阵中的列和行，而不是常规的坐标系。
时间复杂度为O(t)，其中t是给定的时间单位。空间复杂度为O(w*h)，用于存储矩阵。对于给定的数据范围（w,h<100, t<100），这个算法可以高效地解决问题。
参考代码
- Python
import sys
input = lambda:sys.stdin.readline().strip()
# 读取输入第一行的参数
w, h, x, y, sx, sy, t = map(int, input().split())
# 读取矩阵
matrix = []
for _ in range(h):
matrix.append(input())
# 统计经过1的次数
count = 0
# 模拟移动过程
while t >= 0:
# 检查当前位置是否为1
if matrix[y][x] == '1':
count += 1
# 移动到下一个位置
x += sx
y += sy
# 处理边界反射
if x < 0:
x = 1
sx = -sx
elif x >= w:
x = w - 2
sx = -sx
if y < 0:
y = 1
sy = -sy
elif y >= h:
y = h - 2
sy = -s剩余60%内容，订阅专栏后可继续查看/也可单篇购买
算法刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记
查看9道真题和解析