#504. 「新年欢乐赛 2019」generals

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wahacer

题目描述

题目背景

wahagay 从家里拿了一副将军棋;于是 \ldots 它就姓小了。既然有这么个 rbq ,机房里的 gayiers 肯定不会放过它,于是就有人提出:全机房一起下将军棋。

题目描述

棋盘是一个大小为 n \times m (0 < n,m \le 5000) 的网格,只能在可行的格子里下棋(有些格子不能下棋),机房里一共有 p ( p \le 9) 个人。

棋局开始时,每个人都会有几个初始的城堡,因为人的年龄不同,扩张的速度 speed 也会不同(第 i 个人行动时,可以将离自己的城堡曼哈顿距离不超过 speed 且没有城堡的格子占领,并在这次行动结束后在新占领的格子上建造城堡)。

现在,规定每轮中每人只能行动一次,且一轮行动中的行动顺序也已经确定, wahagay 想让你帮他算一下每个人可以占领多少个格子。

输入格式

第一行包括三个数 n,m,p (0 < n,m \le 5000 ,0<p \le 9) 三个数,表示棋盘的长宽及人数;

接下来一行包括 p 个数 s_i(0 \le s_i \le 500) 表示第 i 个人的行动速度;

之后的 n 行表示棋盘: . 表示可行的格子, \# 表示不可行的格子,若为数字 k 则表示第 k 个人的初始城堡。

输出格式

一行 p 个数,第 i 个数表示第 i 个人占领的格子个数,相邻数之间空格隔开。

样例

样例输入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

样例解释

在样例1中:

第一轮 : 1 先行动占领了与 (1,1) 相邻的格子, 2 占领了与 (3,3) 相邻的格子;

第二轮 : 1 占领与 (1,2),(2,1) 相邻的格子。

数据范围与提示

对于 5 \% 的数据: n,m \le 10,p \le 1

对于 30 \% 的数据: n,m \le 100,p \le 9

对于 60 \% 的数据: n,m \le 1000 , p \le 9

对于 100 \% 的数据: n,m \le 5000 , p \le 9