Start: Oct, 04, 2021 14:00:00
动态规划强化练习题单
End: Oct, 23, 2021 18:00:00
Time elapsed:
Time remaining:

【NOIP模拟赛A13】填字谜 1276

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:1     AC:1     Score:100


Description

和其他农夫一样,约翰也非常喜欢玩填字游戏。但是,不幸的事情还是发生了,他妹妹把咖啡撒在了他的本子上,很难看清楚上面的内容。现在,你的任务是,帮助约翰尽可能地恢复填字游戏的编号。

给你一个n*m的矩阵(3 <= N <=50, 3 <= M <= 50),一些格子是清楚的,用‘.’表示,还有一些格子是不清楚的,用‘#’表示。你需要按下面的步骤给恢复填字游戏的编号:

1.找到每个字谜的起始格,满足下面条件的格子可以作为字谜的起始格:

a、如果作为水平方向的起始格,那么,当前格子的左边一格必须是‘#’(每行的第一格例外),右边两格为‘.’;

b、如果作为垂直方向的起始格,那么,当前格子的上面一个格子必须是‘#’(每列的第一格例外),下方的两格格子为‘.’;

c、‘#’不可以作为起始格。

2.找到所有的起始格之后,按从上到下,从左往右的顺序,给每个格子编号,编号从1开始。


比如说,给你的矩阵是这样的:

...

#..

...

..#

.##

第一步,找到所有的起始格(用!表示起始格):


!!!

#..

!..

..#

.##

第二步,给起始格编号:

123

#..

4..

..#


.##

Input

输入第一行包含两个数字:n,m。接下来输入一个n*m的矩阵,矩阵由‘.’和‘#’组成。

Output

首先输出一个整数x,表示能够确定的起始格数量,接下来按顺序输出x行,每行两个整数,表示对应格子的行号和列号。

Samples

input:
5 3 ... #.. ... ..# .##
output:
4 1 1 1 2 1 3 3 1