刷题笔记合集🔗

反射计数

问题描述

给定一个包含 0 和 1 的二维矩阵。

给定一个初始位置和速度，一个物体从给定的初始位置出发，在给定的速度下进行移动，遇到矩阵的边缘则发生镜面反射。

无论物体经过 0 还是 1，都不影响其速度。

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

矩阵以左上角位置为 （列()，行()），例如下面 A 点坐标为 （第二列，第一行）

注意：

1. 如果初始位置的点是 1，也计算在内
2. 时间的最小单位为 1，不考虑小于 1 个时间单位内经过的点

输入格式

第一行为初始信息，包含七个整数 、、、、、、，分别表示：

• ， 为矩阵的宽和高
• ， 为起始位置
• ， 为初始速度
• 为经过的时间

第二行开始一共 行，为二维矩阵信息，每行包含 个字符，只有 0 和 1。

输出格式

输出一个整数，表示经过 1 的个数。

注意初始位置也要计算在内。

样例输入

12 7 2 1 1 -1 13
001000010000
001000010000
001000010000
001000010000
001000010000
001000010000
001000010000

样例输出

3

数据范围

题解

这道题目模拟了一个物体在二维矩阵中移动的过程，要求统计它经过值为1的格子的次数。

主要难点在于处理边界反射的逻辑。当物体到达矩阵边界时，需要按照镜面反射的规则改变其速度方向并计算新的位置。

解题思路：

1. 首先解析输入，获取矩阵尺寸、初始位置、初始速度和时间。
2. 然后，模拟物体在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 = -