← 返回题目列表

AtCoder · past202206_f

F. 枪射击

中文机器翻译题面 查看原题

分数: 7 点

问题陈述

高桥正在玩射击游戏。 游戏画面有一个网格 H 水平行和 W 垂直列。 广场位于 i-th (1 \leq i \leq H) 从顶部开始行, j-th (1 \leq j \leq W) 网格中左侧的列称为 (i, j)。 每个正方形要么是一个 空方块 或 砖方。 每个砖块都涂有正整数代表的颜色。

广场的状态 (i, j) 用非负整数表示 S_{i, j}。 如果 S_{i,j} = 0,则该方格为空方格;如果 S_{i, j} 是一个正整数,那么这个正方形就是一个颜色的砖块正方形 S_{i, j}.

让我们称行中除 H- 从上往下数第 a 浮砖 如果下面的相邻方块是空方块。 最初,没有浮砖。

现在,高桥就可以了 N 操作中, i-th (1 \leq i \leq N) 其中如下:

  • 拍摄方形 (r_i, c_i)。 如果该方格是空方格,则不会发生任何事情;如果它是一个砖块方块,它会变成一个空方块。
  • 然后,所有漂浮的砖块都会掉落。 严格来说,执行以下操作直到没有浮砖为止:
    • 选择一块浮动砖块并将该方块与下面相邻的方块交换。

打印之后每个方块的状态 N 操作已完成,格式与 S_{i, j}.

约束

  • 1 \leq H, W \leq 100
  • 0 \leq S_{i, j} \leq 10^9 \, (1 \leq i \leq H, 1 \leq j \leq W)
  • If S_{i, j} > 0,那么 S_{i + 1, j} > 0 \, (1 \leq i \leq H - 1, 1 \leq j \leq W).
  • 1 \leq N \leq 10^3
  • 1 \leq r_i \leq H \, (1 \leq i \leq N)
  • 1 \leq c_i \leq W \, (1 \leq i \leq N)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

H W
S_{1, 1} \ldots S_{1, W}
\vdots
S_{H, 1} \ldots S_{H, W}
N
r_1 c_1
\vdots
r_N c_N

输出

打印 H 行。 每行应包含 W 由空格分隔的整数,以满足以下条件:

  • 的 j-th (1 \leq j \leq W) 中的整数 i-th (1 \leq i \leq H) 行应该是 0 如果正方形 (i, j) 是 Takahashi 之后的一个空方块 N 操作已完成;如果它最终是一个砖块方块,它应该是代表其颜色的整数。

示例输入 1

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

示例输出 1

0 0 0
1 1 0
3 2 4

当他拍摄 Square 时 (3, 2),网格过渡如下:

0 1 0 \quad       0 1 0 \quad       0 1 0 \quad       0 0 0
1 2 0 \rightarrow 1 2 0 \rightarrow 1 0 0 \rightarrow 1 1 0
3 4 4 \quad       3 0 4 \quad       3 2 4 \quad       3 2 4

示例输入 2

1 1
1
1
1 1

示例输出 2

0

示例输入 3

2 3
18459 0 35959
150312 573935 612940
3
2 3
1 2
1 1

示例输出 3

0 0 0
150312 573935 35959