Jeopardy of Dropped Balls

题意翻译

Chanek 先生发明了一个叫做 _Dropping Balls_ 的新游戏。一开始，Chanek 先生有一个大小为 $n\times m$ 的网格图 $a$。第 $x$ 行第 $y$ 列被记为 $(x,y)$，里面包含一个整数 $a_{x,y}$，表示在 $(x,y)$ 的小球将要到达的位置。具体地： - 如果 $a_{x,y}=1$，则这个小球将会向右移动到 $(x,y+1)$。 - 如果 $a_{x,y}=2$，则这个小球将会向右移动到 $(x+1,y)$。 - 如果 $a_{x,y}=3$，则这个小球将会向右移动到 $(x,y-1)$。 特别地，如果一个小球经过了 $(x,y)$，则 $a_{x,y}$ 变为 $2$。 现在，Chanek 先生要丢下 $k$ 个小球，第 $i$ 个小球从第一行第 $c_i$ 列开始掉落。请你帮 Chanek 先生预测每个小球最终会落在哪一列。 数据范围： - $1\leqslant n,m\leqslant 1000$，$1\leqslant k\leqslant 10^5$。 - $1\leqslant a_{i,j}\leqslant 3$，$1\leqslant c_i\leqslant m$。 Translated by Eason_AC 2021.12.29

题目描述

Mr. Chanek has a new game called Dropping Balls. Initially, Mr. Chanek has a grid $ a $ of size $ n \times m $ Each cell $ (x,y) $ contains an integer $ a_{x,y} $ denoting the direction of how the ball will move. - $ a_{x,y}=1 $ — the ball will move to the right (the next cell is $ (x, y + 1) $ ); - $ a_{x,y}=2 $ — the ball will move to the bottom (the next cell is $ (x + 1, y) $ ); - $ a_{x,y}=3 $ — the ball will move to the left (the next cell is $ (x, y - 1) $ ). Every time a ball leaves a cell $ (x,y) $ , the integer $ a_{x,y} $ will change to $ 2 $ . Mr. Chanek will drop $ k $ balls sequentially, each starting from the first row, and on the $ c_1, c_2, \dots, c_k $ -th ( $ 1 \leq c_i \leq m $ ) columns. Determine in which column each ball will end up in (position of the ball after leaving the grid).

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , and $ k $ ( $ 1 \leq n, m \leq 1000 $ , $ 1 \leq k \leq 10^5 $ ) — the size of the grid and the number of balls dropped by Mr. Chanek. The $ i $ -th of the next $ n $ lines contains $ m $ integers $ a_{i,1},a_{i,2},\ldots,a_{i,m} $ ( $ 1 \leq a_{i,j} \leq 3 $ ). It will satisfy $ a_{i, 1} \ne 3 $ and $ a_{i, m} \ne 1 $ . The next line contains $ k $ integers $ c_1, c_2, \ldots, c_k $ ( $ 1 \leq c_i \leq m $ ) — the balls' column positions dropped by Mr. Chanek sequentially.

输出格式

Output $ k $ integers — the $ i $ -th integer denoting the column where the $ i $ -th ball will end.

输入输出样例

输入样例 #1

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

输出样例 #1

2 2 1

输入样例 #2

1 2 2
1 3
1 2

输出样例 #2

1 2

说明

In the first example, the first ball will drop as follows. Note that the cell $ (1, 1) $ will change direction to the bottom direction. The second and third balls will drop as follows. All balls will be dropped from the first row and on the $ c_1, c_2, \dots, c_k $ -th columns respectively. A ball will stop dropping once it leaves the grid.