首页 > 试题广场 >

棋盘

[编程题]棋盘
  • 热度指数：582 时间限制：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) 向下滚动一格即抵达  。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n\left( 1 \le n \le 500\right) 代表棋盘大小。
\,\,\,\,\,\,\,\,\,\,此后 n 行，每行输入 n 个整数 a_1,a_2,\dots,a_n\left( 0\le a_i\le 1\right) 代表棋盘上每个格子上写的数字。
\,\,\,\,\,\,\,\,\,\,第 n+2 行输入一个整数 q \left(1\leq q \leq 2\times 10^5 \right) 代表询问次数。
\,\,\,\,\,\,\,\,\,\,随后 q 行，每行输入四个整数 x_1,y_1,x_2,y_2\left(1 \leq x_1, x_2 , y_1, y_2 \leq n ;\ x_1 \leq x_2;\ y_1 \leq y_2\right) 代表子矩阵范围。


输出描述:
\,\,\,\,\,\,\,\,\,\,对于每一次询问，在一行上输出两个整数，代表小球滚出的位置。
示例1

输入

4
1 0 0 1
0 0 1 1
1 0 1 0
0 1 1 1
2
2 2 4 4
2 3 3 3

输出

4 4
2 3

说明

\,\,\,\,\,\,\,\,\,\,对于第一次询问，子矩阵为下划线部分数字 \begin{bmatrix}<br /> 1 & 0 & 0 & 1\\<br /> 0 & \underline0 & \underline1 & \underline1\\<br /> 1 & \underline0 & \underline1 & \underline0\\<br /> 0 & \underline1 & \underline1 & \underline1<br />\end{bmatrix} ，我们描述滚动全过程：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 从 (2,2) 出发，由于该单元格为 0 ，向下滚动；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 从 (3,2) 继续，由于该单元格为 0 ，向下滚动；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 从 (4,2) 继续，由于该单元格为 1 ，向右滚动；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 从 (4,3) 继续，由于该单元格为 1 ，向右滚动；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 从 (4,4) 继续，由于该单元格为 1 ，向右滚动；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 滚出边界，结束。
示例2

输入

5
1 0 0 1 1
1 1 0 1 0
0 0 1 1 1
0 1 0 1 1
1 1 1 1 0
2
2 2 3 5
1 1 5 5

输出

3 5
3 5
算法知识视频讲解
开通博客
头像 想run的秋田犬在写文章
发表于 2025-08-05 20:04:45
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 猫狗Cola
发表于 2025-07-26 11:31:48
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<vector<int>> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 v3m0uth
发表于 2025-07-26 14:32:27
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; cin >> n; vec 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 立夏0218
发表于 2025-07-26 18:15:51
#include <stdio.h> #include <stdlib.h> int main() { int n; scanf("%d", &n); // 动态分配棋盘内存 int **board = (int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 姜晓雯
发表于 2025-08-01 21:52:38
#include <iostream> #include <vector> using namespace std; int main() { int size; cin >> size; vector<vector<int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 有胆量的柯基在学习
发表于 2025-08-20 20:14:40
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<vector<int>> a(n + 1, vector&l 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数组 模拟 饿了么
难度：
1条回答 211浏览

热门推荐

相关试题

棋盘

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号