和其他农夫一样,约翰也非常喜欢玩填字游戏。但是,不幸的事情还是发生了,他妹妹把咖啡撒在了他的本子上,很难看清楚上面的内容。现在,你的任务是,帮助约翰尽可能地恢复填字游戏的编号。
给你一个n*m的矩阵(3 <= N <=50, 3 <= M <= 50),一些格子是清楚的,用‘.’表示,还有一些格子是不清楚的,用‘#’表示。你需要按下面的步骤给恢复填字游戏的编号:
1.找到每个字谜的起始格,满足下面条件的格子可以作为字谜的起始格:
a、如果作为水平方向的起始格,那么,当前格子的左边一格必须是‘#’(每行的第一格例外),右边两格为‘.’;
b、如果作为垂直方向的起始格,那么,当前格子的上面一个格子必须是‘#’(每列的第一格例外),下方的两格格子为‘.’;
c、‘#’不可以作为起始格。
2.找到所有的起始格之后,按从上到下,从左往右的顺序,给每个格子编号,编号从1开始。
比如说,给你的矩阵是这样的:
...
#..
...
..#
.##
第一步,找到所有的起始格(用!表示起始格):
!!!
#..
!..
..#
.##
第二步,给起始格编号:
123
#..
4..
..#
.##
输入第一行包含两个数字:n,m。接下来输入一个n*m的矩阵,矩阵由‘.’和‘#’组成。
首先输出一个整数x,表示能够确定的起始格数量,接下来按顺序输出x行,每行两个整数,表示对应格子的行号和列号。