哈喵~ 主人，今天我们来看一道有趣的模拟题喵！这道题就像一个精心设计的弹珠台，让我们一起来看看小球是怎么在里面蹦跶的吧！

J. Jeopardy of Dropped Balls (1575J)

---

题目大意

这道题呀，就像一个弹珠游戏喵。我们有一个 n x m 大小的网格，每个格子里都有一个数字，告诉弹珠下一步该往哪儿走：

• 1: 向右移动一格。
• 2: 向下移动一格。
• 3: 向左移动一格。

最关键的规则是：每当一个弹珠从某个格子 (x, y) 离开后，这个格子的方向数字就会立刻变成 2（向下）。

现在，我们要按顺序扔下 k 个弹珠。每个弹珠都从第一行开始，分别落在第 c_1, c_2, ..., c_k 列。我们的任务是，对于每一个弹珠，计算出它最终会从网格的哪一列掉出去。

---

解题方法

一开始看到要模拟 k 个球，而且 k 最大有 10^5，可能会觉得时间会不够用，对吧喵？如果每个球都要在 n x m 的格子里走很多步，那肯定会超时的。

但是这里有个很重要的机关喵！就是每个格子在弹珠经过之后，方向就会永远变成 ‘向下’（数字2）。

这意味着什么呢？ 一个格子，如果它初始方向是向左（3）或向右（1），那么它只会被第一个经过它的小球“横向”地穿过。一旦这个小球离开，这个格子就变成了“直通车”，之后所有到达这个格子的小球都只会直直地掉下去，不会再有任何横向移动了。

所以，整个网格中，所有格子的横向移动（向左或向右）加起来，最多只会被触发 n * m 次。在这之后，整个网格就变成了一个“瀑布”，所有小球都会笔直下落。

基于这个发现，我们可以得出一个结论：直接按照题目要求，一个一个地模拟小球的下落过程，是完全可行的喵！因为总的计算量并不会爆炸。

所以，我们的解法就是：

1. 读入网格和 k 个小球的初始列。
2. 循环 k 次，每次处理一个小球。
3. 在每次循环中，模拟当前小球的运动轨迹：
   • 从第一行、指定的列开始。
   • 根据当前格子的方向数字移动。
   • 在离开当前格子后，立刻把这个格子的方向数字更新为 2。
   • 重复这个过程，直到小球的行坐标超出了网格范围（即 r >= n）。
4. 记录小球离开网格时的列坐标，并输出。

---

题解代码

让本喵来带你一步一步看懂这段代码吧喵~

#include <iostream>
#include <vector>

// 这是一个小魔法，能让 C++ 的输入输出变得飞快，对付大数据量的题目很有用喵。
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

int main() {
    // 开启高速模式！
    fast_io();

    // 读入网格的行数 n, 列数 m, 以及小球的数量 k
    int n, m, k;
    std::cin >> n >> m >> k;

    // 用一个叫 vector 的二维数组 a 把整个地图存起来。
    // 我们这里用 0-indexed，也就是行从 0 到 n-1，列从 0 到 m-1，这样写代码更方便喵。
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }

    // 读入 k 个小球的起始列
    std::vector<int> start_cols(k);
    for (int i = 0; i < k; ++i) {
        std::cin >> start_cols[i];
    }

    // 接下来就是一个大循环，从第 1 个球到第 k 个球，一个一个地放
    for (int i = 0; i < k; ++i) {
        // 小球的当前位置 (r, cur_c)，也是 0-indexed
        // 小球从第 0 行开始
        int r = 0;
        // 题目的列是 1-indexed，我们要转成 0-indexed，所以要减 1
        int cur_c = start_cols[i] - 1; 

        // 在这个 while 循环里，我们模拟一个小球的下落过程。
        // 只要小球还在网格里 (r < n)，它就会一直移动
        while (r < n) {
            int dir = a[r][cur_c];
            
            // 这就是这道题的精髓所在喵！
            // 每当小球离开一个格子 (r, cur_c)，我们就立刻把这个格子的方向改成 2（向下）。
            a[r][cur_c] = 2;

            if (dir == 1) {
                // 方向 1：向右走
                cur_c++;
            } else if (dir == 2) {
                // 方向 2：向下走
                r++;
            } else { // dir == 3
                // 方向 3：向左走
                cur_c--;
            }
        }

        // 当小球终于掉出网格（也就是 r 大于等于 n 了），循环就结束了。
        // 这时候 cur_c 就是小球最终所在的列啦。
        // 记得要把它从 0-indexed 变回 1-indexed（加1）再输出哦喵~
        // (i == k - 1 ? "" : " ") 是为了控制输出格式，最后一个数字后面没有空格。
        std::cout << cur_c + 1 << (i == k - 1 ? "" : " ");
    }

    // 最后输出一个换行符，是个好习惯喵。
    std::cout << "\n";

    return 0;
}

---

知识点介绍

这道题主要用到了下面这些知识点，喵~

1. 模拟 (Simulation) 模拟题就是计算机扮演一个角色，按照题目给定的规则一步一步地执行操作，最后得出结果。就像我们这次，让电脑去模拟小球掉落的过程。模拟题的关键在于正确理解和实现题目中的所有规则，特别是那些会改变状态的规则（比如这道题里格子方向的变化）。

2. 二维数组/向量 (2D Array/Vector)std::vector<std::vector<int>> 是 C++ 中表示二维数组的常用方法。它非常适合用来存储像本题中的网格一样的二维数据结构。

3. 时间复杂度分析 (Time Complexity Analysis) 这是本题解法的核心！为什么这个方法不会超时呢？关键就在于那个“格子方向会变”的规则。

   • 一个格子，如果它的方向是向左（3）或向右（1），那它最多只会被一个小球“横着”穿过一次。一旦穿过，它就变成了向下（2）。之后所有的小球经过这里都只会直直地掉下去。
   • 所以，所有小球加起来，横向移动的总次数不会超过整个网格的格子数 n * m。
   • 每个小球最多向下移动 n 次，k 个小球的向下移动总次数是 k * n。
   • 因此，总的计算量大概是 O(n * m + k * n)，对于这道题的 n, m <= 1000, k <= 10^5 的范围来说，是完全可以接受的喵！

好啦，这道题的讲解就到这里啦。是不是很简单呢喵？只要抓住了那个“格子会变身”的关键点，问题就迎刃而解了。主人下次再见喵~ >w<