← 返回题目列表

Codeforces · 1105/D

D. 基拉尼和游戏

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

Kilani 正在和他的朋友们玩游戏。这个游戏可以表示为一个大小为 $$$n \times m$$$ 的网格,其中每个单元格要么是空的,要么是被封锁的,并且每个玩家在某些单元格中拥有一个或多个城堡(一个单元格中没有两个城堡)。

比赛按回合进行。在每一轮中,玩家依次展开:首先,第一个玩家展开,然后第二个玩家展开,依此类推。扩张过程如下:对于玩家现在拥有的每座城堡,他都会尝试扩张到附近的空单元格。玩家$$$i$$$可以从一个有他的城堡的单元格扩展到空的单元格,如果可以在最多$$$s_i$$$(其中$$$s_i$$$是玩家的扩展速度)移动到左、上、右或下而不穿过被阻挡的单元格或被其他玩家的城堡占据的单元格的情况下到达它。玩家检查他可以扩展到的单元格集合,并立即在每个单元格中建造一座城堡。之后,回合将传递给下一个玩家。

当没有玩家可以移动时游戏结束。每个玩家都会获得游戏场地和扩张速度。 Kilani 想知道每个玩家在游戏结束后将控制多少个单元格(拥有自己的城堡)。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$p$$$ ($$$1 \le n, m \le 1000$$$, $$$1 \le p \le 9$$$) — 网格的大小和玩家的数量。

第二行包含 $$$p$$$ 整数 $$$s_i$$$ ($$$1 \le s \le 10^9$$$) — 每个玩家的扩张速度。

以下 $$$n$$$ 行描述了游戏网格。它们每个都由 $$$m$$$ 符号组成,其中“.”表示空单元格,“#”表示被阻止的单元格,数字 $$$x$$$ ($$$1 \le x \le p$$$) 表示玩家 $$$x$$$ 拥有的城堡。

保证每个玩家在网格上至少拥有一座城堡。

输出

打印 $$$p$$$ 整数 - 游戏结束后每个玩家控制的单元格数量。

示例

输入 #1

3 3 2
1 1
1..
...
..2

输出 #1

6 3

输入 #2

3 4 4
1 1 1 1
....
#...
1234

输出 #2

1 4 3 3

注意

下图为第一个示例中比赛开始前、第一轮后和第二轮后的比赛:

在第二个示例中,第一个玩家被“阻止”,因此他不会在整个游戏中捕获新的单元格。在前两轮中,所有其他玩家都会向上扩展,在第三轮中,只有第二名玩家会向左移动。