#5644. 「PA 2014 Final」Gra w podwajanie

标签: 传统 | 时间限制: 14500 ms | 内存限制: 128 MiB |

题目描述

翻倍游戏与其说是一项游戏，不如说更像是一场解谜。游戏棋盘呈长方形，被划分为若干个单位正方形格子。初始时，某些格子里放有一个筹码，而另一些格子则是空的。

玩家的目标是在单个格子里收集尽可能多的筹码。唯一可执行的操作是：在棋盘上寻找两个相邻（共有边界）且含有相同（正数）筹码数的格子，然后将其中一格的所有筹码全部移入另一格中。

请编写一个程序，对于给定的棋盘初始配置，计算每个格子最终能收集到的最大筹码数量。

输入的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 200)$ ，分别代表棋盘的行数和列数。

接下来的 $n$ 行中，每行包含一个由 $m$ 个数字 $0$ 或 $1$ 组成的字符串。数字 $1$ 表示该格子里初始有一个筹码，数字 $0$ 则表示该格子为空。

你的程序应当输出 $n$ 行，每行包含 $m$ 个整数。其中第 $i$ 行的第 $j$ 个数字应表示：从给定的初始配置开始，玩家在第 $i$ 行第 $j$ 列的格子里最终所能收集到的最大筹码数量。

输入

输出

0 2 4 4
2 0 4 4
2 0 4 4

上图说明了如何在中间行和最后一列的交叉格子中收集到 $4$ 个筹码。