纵横字谜

题目描述

像其他奶牛一样，奶牛贝茜喜欢解纵横字谜。

不幸的是，她的妹妹艾希将牛奶洒到了她的纵横字谜书上，弄脏了文字，让她很难看出每个单词的填写起点。

请帮助贝茜将每个单词起点找出，并将它们标号。

一个未标记的纵横字谜以 $N\times M$ 的网格形式给出。

其中一些单元格是白色的，一些单元格是黑色的。

白色的方格组成一些交叉的行与列，我们要将单词填入至这些行与列中，每个白色方格只能填入一个字母。 （上图是一个填字游戏的参考图，其中被数字标记的是各个横纵单词的起点，当然在本题中，各个单词的起点被牛奶遮盖住了，我们需要自己找出）

在这种布局下，找出并标记每个单词的起点是一个简单的过程，遵循两个逻辑步骤：

步骤一：对于每个单元格，我们需要确定其是否可以作为一个水平单词或垂直单词的起点。如果某个单元格可以作为一个水平单词的起点，则该单元格必须是白色单元格，其左侧相邻单元格必须是黑色单元格或者其左侧没有相邻单元格（即处于边界位置），并且其右侧的前两个单元格必须是白色单元格（也就是说，水平单词至少要包含 $3$ 个字母）。判断单元格是否可以作为一个垂直单词的起点的规则是相似的：该单元格必须是白色单元格，其上方相邻单元格必须是黑色单元格或者其上方没有相邻单元格，其下方的前两个单元格必须是白色单元格。

步骤二：我们给每个可以作为单词起点的单元格标记一个数字。按照从上到下，每行从左到右的顺序，依次标记每个满足条件的单元格。标记数字从 $1$ 开始，依次递增。不能作为单词起点的单元格不用标记。

例如，考虑以下网格，其中 “.” 代表白色单元格，”#” 代表黑色单元格。

...
#..
...
..#
.##

可以作为水平或垂直单词起点的单元格标记为 “!”，如下所示：

!!!
#..
!..
..#
.##

将这些被标记的单元格依次编号，我们最终得到：

123
#..
4..
..#
.##

注意，输入数据中描述的纵横字谜可能不满足媒体上发布的纵横字谜的限制。

例如，一些白色单元格可能不属于任何单词的一部分。

输入格式

第一行包含整数 $N$ 和 $M$。 接下来 $N$ 行，描述字母网格，每行包含 $M$ 个字符，其中 . 表示白色单元格，# 表示黑色单元格。

输出格式

第一行，输出可作为单词开头的单元格的数量。 接下来若干行，按照标记数字顺序，每行输出一个可作为单词开头的单元格的位置。 左上角单元格的位置为 $(1,1)$，右下角单元格的位置为 $(N,M)$。

5 3
...
#..
...
..#
.##

4
1 1
1 2
1 3
3 1

提示

#### 数据范围 $3\le N,M\le 50$

来源

童程童美