USACO2014DEC 铜组第二题

题目描述

和所有奶牛一样，贝茜（Bessie）喜欢玩填字游戏。不幸的是，她的姐妹艾尔西（Elsie）把牛奶洒在了填字游戏书上，弄脏了文字，让贝茜很难看清每个线索的起始位置。你的任务是帮贝茜恢复线索编号。

一个未标记的填字游戏由 ( N * M )（( 3 <= N, M <= 50 ) ）的网格表示，其中一些格子是空白（用 . 表示，通常为白色 ），一些是阻塞（用 # 表示，通常为黑色 ）。根据这个布局，线索编号遵循以下两个逻辑步骤：

步骤 1：判断线索起始格

需确定每个空白格是否是水平线索起始格或垂直线索起始格：

• 水平线索起始格：该格子是空白，且左侧相邻格子是阻塞或在网格外；同时右侧至少有 2 个连续空白格（即，水平线索需表示长度 ≥3 的单词 ）。
• 垂直线索起始格：该格子是空白，且上方相邻格子是阻塞或在网格外；同时下方至少有 2 个连续空白格（即，垂直线索需表示长度 ≥3 的单词 ）。

步骤 2：分配线索编号

对每个线索起始格分配编号，编号规则与阅读书籍顺序一致：

• 按行优先顺序遍历网格（先第一行，再第二行…… ）。
• 每行内从左到右遍历。
• 仅对线索起始格分配编号，从 1 开始递增。

输入格式

• 第 1 行：两个整数 ( N ) 和 ( M )，表示网格的行数和列数。
• 第 2 至 ( N+1 ) 行：每行包含 ( M ) 个字符，描述网格的一行，字符为 .（空白）或 #（阻塞 ）。

样例输入

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

输入详情
5 行 3 列的网格，需按规则判断线索起始格并编号。

输出格式

• 第 1 行：线索的总数量。
• 后续每行：按编号顺序，输出线索起始格的行号和列号（行、列编号从 1 开始，左上角为 (1,1)，右下角为 (N,M) ）。

样例输出

4
1 1
1 3
3 1
3 3

输出详情
根据规则，找到 4 个线索起始格，按行优先顺序编号并输出其坐标。