logo AlgoBeat OnlineJudge
登录 注册

#10042. 犇犇的领地

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

题目描述

在一块面积为 正方形的空地上,我们知道有 个犇犇。

这块空地被分成 块不同的区域,由于犇犇的领地意识极强所以保证每个的区域内都只有一个犇犇,且以某个犇犇为中心的九宫格内只有它一只犇犇

可每个犇犇视力不太好,它只能看见和它同一行同一列的其他领地。所以在和犇犇同一行同一列的区域上也不能有其他犇犇

一个犇犇找到你,想让你帮它找出除已知犇犇的其他犇犇的总数以及位置

输入格式

第一行一个整数 代表空地的边长。

第二行一个整数 ,表示区域总数。

第三行一个整数 ,表示知道的犇犇的数量。

行,为一个正方形矩阵由大写字母组成,表示不同的区域:

  • 每个大写字母所占面积就是一个区域。
  • 时,一些大写字母会被替换为 * 表示已知的每只犇犇的位置。

已知的犇犇的所属区域与它上方的大写字母的领地阵营一样,如果上方没有大写字母那就与它下方的大写字母的所属区域一样。

输出格式

第一行一个整数 ,表示除已知犇犇的其他犇犇的总数
如果 ,那么只输出 No Benben

行一个大写字母,在加上这只犇犇的坐标,表示它是某个区域的犇犇。例如:G 1,1,表示它在 G 阵营坐标是

区域按字典序输出。

样例

输入#1

5
5
1
A A B B B
A A A A C
A * D D C
D D D E C
D D E E E

输出 #1

4
B 1,3
C 2,5
D 5,1
E 4,4

数据范围与提示

【样例解释 #1】
1 表示不能有犇犇的区域,@ 表示除已知犇犇其他犇犇的位置。
因为 * 上方是 A 区域,所以 * 属于 A 区域,又因为一个区域只能有一只犇犇且在和犇犇同一行同一列的区域上也不能有其他犇犇。所以可得出:

1 1 B B B
1 1 1 1 C
1 * 1 1 1
1 1 1 E C
D 1 E E E

此时 D 区域只剩一格而每个区域都有一个犇犇,所以可得出:

1 1 B B B
1 1 1 1 C
1 * 1 1 1
1 1 1 E C
@ 1 1 1 1

此时 E 区域只有一格,可得出:

1 1 B B B
1 1 1 1 C
1 * 1 1 1
1 1 1 @ 1
@ 1 1 1 1

此时 C 区域只有一格,可得出:

1 1 B 1 1
1 1 1 1 @
1 * 1 1 1
1 1 1 @ 1
@ 1 1 1 1

此时 B 区域只有一格,可得出最终图形:

1 1 @ 1 1
1 1 1 1 @
1 * 1 1 1
1 1 1 @ 1
@ 1 1 1 1

保证正方形空地都由大写字母和 * 组成。

【数据范围】

测试点编号

对于一些数据,当 时有一个区域只有一格。