首页 > 试题广场 >

棋盘

[编程题]棋盘

热度指数：555 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\,\,\,\,\,\,\,\,\,\,$ 有一个 $n$ 行 $n$ 列的棋盘，每个格子上写着数字 $0$ 或 $1$ 。有一个小球从某个格子出发，移动到写着 $0$ 的格子时会向下移动一格；移动到写着 $1$ 的格子时会向右移动一格，直到滚出棋盘边界。

$\,\,\,\,\,\,\,\,\,\,$ 现在有 $q$ 个询问，每次询问在子矩阵 $(x_1,y_1)\sim(x_2,y_2)$ 中，小球从 $(x_1,y_1)$ 出发开始滚动，最后会从哪个格子滚出子矩阵 $(x_1,y_1)\sim(x_2,y_2)$ 。

$\,\,\,\,\,\,\,\,\,\,$ 从某个格子滚出子矩阵 $(x_1,y_1)\sim(x_2,y_2)$ ，意思是当前所在的格子在子矩阵内，但是小球滚动路径的下一个格子不在子矩阵内，视为滚出。

$\,\,\,\,\,\,\,\,\,\,$ 从棋盘 $(x,y)$ 向右滚动一格即抵达 $(x,y+1)$ ，从棋盘 $(x,y)$ 向下滚动一格即抵达 $(x+1,y)$ 。

输入描述:

第一行输入一个整数  代表棋盘大小。
此后  行，每行输入  个整数  代表棋盘上每个格子上写的数字。
第  行输入一个整数  代表询问次数。
随后  行，每行输入四个整数  代表子矩阵范围。

输出描述:

对于每一次询问，在一行上输出两个整数，代表小球滚出的位置。

示例1

输入

输出

4 4
2 3

说明

对于第一次询问，子矩阵为下划线部分数字  ，我们描述滚动全过程：
● 从  出发，由于该单元格为  ，向下滚动；
● 从  继续，由于该单元格为  ，向下滚动；
● 从  继续，由于该单元格为  ，向右滚动；
● 从  继续，由于该单元格为  ，向右滚动；
● 从  继续，由于该单元格为  ，向右滚动；
● 滚出边界，结束。

示例2

输入

输出

3 5
3 5

算法知识视频讲解

Python3

牛客192469163号

import sys

input = sys.stdin.readline

def main():

n = int(input())

grid = [list(map(int, input().split())) for _ in range(n)]

q = int(input())

for _ in range(q):

x1, y1, x2, y2 = map(int, input().split())

# 转成 0-index

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

i, j = x1, y1

while i <= x2 and j <= y2:

if grid[i][j] == 0:

i += 1

else:

j += 1

# 输出时转回 1-index

if i > x2:

print(x2 + 1, j + 1)

if j > y2:

print(i + 1, y2 + 1)

if __name__ == "__main__":

main()

发表于 2025-09-03 12:45:05 回复(0)

提交观点

问题信息

数组模拟饿了么

难度：

1条回答 9收藏 160浏览

棋盘

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题