P6834: 填字游戏

---

【题目描述】

【题目描述】
像所有的奶牛一样，奶牛贝西喜欢玩填字游戏。 不幸的是，她的妹妹埃尔西把牛奶洒在了她填字游戏的书上，把文字涂得乱七八糟，让她看不清每条线索开始的地方。你的工作是帮助贝茜摆脱困境，恢复线索编号!
一个未标记的填字游戏是一个N乘M网格（3<=N<=50、3<=M<=50）。一些单元格是透明的(通常是白色的)，一些单元格会被阻塞(通常是黑色的)。鉴于这种布局，线索编号是一个简单的过程，它遵循两个逻辑步骤:
步骤1:我们确定每个单元格开始是水平的还是垂直的线索。如果一个单元格开始一个水平线索，它必须清楚，它的左边的相邻单元格必须被阻塞或在填字游戏之外网格，其右边的两个单元格必须是清晰的(即a 横向线索只能表示3个或以上字符的单词)。以垂直线索开头的单元格的规则与此类似:单元格上面的格子必须被挡住或在网格外，下面的两个格子必须说清楚。
步骤2:我们为线索开始的每个单元格分配一个数字。单元格是从1开始按相同的顺序分配的数字你会读一本书;第一行中的单元格被分配编号从左到右，然后是第二行，等等。只有细胞开始了线索被分配号码。
例如，考虑网格，其中'.'表示透明单元格和“#”是一个被阻塞的单元格。
...
# . .
...
.. #
.##
可以开始水平或垂直线索的单元格被标记为!
下图:
!!!
#..
!..
..#
.## 
如果我们给这些单元格赋值，我们会得到以下结果;
123
# . .
4 . .
. .#
.# #。
请注意，输入数据中描述的填字游戏可能不满足要求在已出版的填字游戏中常见的约束。例如，一些透明的单元格可能不是任何线索的一部分。
【输入格式】:(crosswords.in)
第一行输入包含N和M，用空格分隔。
接下来的N行输入分别描述网格中的一行。每一个
包含M个字符，可以是'.'(透明单元格)或'#' (阻止单元格)。
【输出格式】:(crosswords.out)
在输出的第一行上，输出线索的数量。
在剩余的每一行上，输出行和列
一条线索的位置(如上所述)。左上角单元格的位置为(1,1)。右下单元格的位置为(N, M)。
【样例输入】:
5 3
...
#..
...
..#
.##
【样例输出】:
4
1 1
1 2
1 3
3 1

题目类型~

USACO-2014-铜-1 

咻咻~

提交答案 状态 返回