棋盘

[题目链接](https://www.nowcoder.com/practice/b8e7884e2cba4646806a90c4a26a65c5)

题意

给定一个 的棋盘，每格写有 或 ：

• 小球在格子为 时向下移动一格；
• 小球在格子为 时向右移动一格；
• 直到移出子矩阵边界为止。

每次询问给定子矩阵 ，小球从 出发，求其滚出子矩阵的位置。

思路

关键观察

小球的运动路径是确定的：从当前格子出发，若格子为 则持续向右，遇到 则转而向下；若格子为 则持续向下，遇到 则转而向右。整个路径由若干段"连续向右"和"连续向下"交替组成。

预处理加速

朴素模拟对每次询问逐格移动为 ，总复杂度 ，可能超时。

优化思路：预处理两个跳转数组，实现每次"换方向"时 到达下一个换向点：

1. next0[i][j]：在第 行，从第 列起向右，第一个值为 的列下标（若不存在则为 ）。
2. next1[i][j]：在第 列，从第 行起向下，第一个值为 的行下标（若不存在则为 ）。

预处理方式：

• next0[i][j]：从右往左扫描每一行，若 grid[i][j] == 0 则 next0[i][j] = j，否则继承 next0[i][j+1]。
• next1[i][j]：从下往上扫描每一列，若 grid[i][j] == 1 则 next1[i][j] = i，否则继承 next1[i+1][j]。

模拟过程（优化版）

对于询问 ，令 ，循环执行：

• 若 grid[r][c] == 1：向右找到 p = next0[r][c]（当前行从 起第一个 ）

- 若 p > c2：无法换向，从右边界滚出，输出 ，结束；

- 否则令 ，继续。

• 若 grid[r][c] == 0：向下找到 p = next1[r][c]（当前列从 起第一个 ）

- 若 p > r2：无法换向，从下边界滚出，输出 ，结束；

- 否则令 ，继续。

每次跳转后 增大或 增大（严格单调），因此每次询问最多跳转 次，总复杂度 。

样例演示

以样例1第一次询问为例：子矩阵 ，起点 。

步骤	当前格	值	操作
1	(2,2)	0	向下找第一个 1，next1[2][2]=4，，移到
2	(4,2)	1	向右找第一个 0，next0[4][2]=n+1（行4全为1在[2,4]内），，滚出右边界

输出 4 4，与期望一致。

复杂度

• 时间：
• 空间：

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 505;
int grid[MAXN][MAXN];
int next0[MAXN][MAXN]; // next0[i][j]: 第i行从j起第一个0的列
int next1[MAXN][MAXN]; // next1[i][j]: 第j列从i起第一个1的行

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> grid[i][j];

    // 预处理 next0：从右往左扫每行
    for(int i = 1; i <= n; i++){
        next0[i][n+1] = n+1;
        for(int j = n; j >= 1; j--)
            next0[i][j] = (grid[i][j] == 0) ? j : next0[i][j+1];
    }

    // 预处理 next1：从下往上扫每列
    for(int j = 1; j <= n; j++){
        next1[n+1][j] = n+1;
        for(int i = n; i >= 1; i--)
            next1[i][j] = (grid[i][j] == 1) ? i : next1[i+1][j];
    }

    int q;
    cin >> q;
    while(q--){
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        int r = r1, c = c1;

        while(true){
            if(grid[r][c] == 1){
                int p = next0[r][c];
                if(p > c2){ cout << r << " " << c2 << "\n"; break; }
                c = p;
            } else {
                int p = next1[r][c];
                if(p > r2){ cout << r2 << " " << c << "\n"; break; }
                r = p;
            }
        }
    }

    return 0;
}

Java 代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        StringBuilder sb = new StringBuilder();

        st.nextToken(); int n = (int)st.nval;
        int[][] grid = new int[n+2][n+2];
        int[][] next0 = new int[n+2][n+2];
        int[][] next1 = new int[n+2][n+2];

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
                st.nextToken();
                grid[i][j] = (int)st.nval;
            }

        for(int i = 1; i <= n; i++){
            next0[i][n+1] = n+1;
            for(int j = n; j >= 1; j--)
                next0[i][j] = (grid[i][j] == 0) ? j : next0[i][j+1];
        }

        for(int j = 1; j <= n; j++){
            next1[n+1][j] = n+1;
            for(int i = n; i >= 1; i--)
                next1[i][j] = (grid[i][j] == 1) ? i : next1[i+1][j];
        }

        st.nextToken(); int q = (int)st.nval;
        while(q-- > 0){
            st.nextToken(); int r1 = (int)st.nval;
            st.nextToken(); int c1 = (int)st.nval;
            st.nextToken(); int r2 = (int)st.nval;
            st.nextToken(); int c2 = (int)st.nval;

            int r = r1, c = c1;
            while(true){
                if(grid[r][c] == 1){
                    int p = next0[r][c];
                    if(p > c2){ sb.append(r).append(' ').append(c2).append('\n'); break; }
                    c = p;
                } else {
                    int p = next1[r][c];
                    if(p > r2){ sb.append(r2).append(' ').append(c).append('\n'); break; }
                    r = p;
                }
            }
        }
        System.out.print(sb);
    }
}