[Usaco2006 Oct]Cows on Skates滑旱冰的奶牛

经过与 Farmer John 长达数年的谈判，奶牛们终于如愿以偿地得到了旱冰鞋。农场的大部分区域都很平整，适合滑行，但有些地块布满岩石，以奶牛们的旱冰技术无法通过。

农场可以看作一个由 $R$ 行、$C$ 列组成的网格。快到晚饭时间了，贝茜位于坐标为 $(1,1)$ 的格子，她想前往坐标为 $(R,C)$ 的牛棚享用晚餐。

贝茜每次可以向上、下、左、右移动到一个相邻格子，但不能沿对角线移动。题目保证存在一条从 $(1,1)$ 到 $(R,C)$ 且不经过任何岩石格子的路径。请输出任意一条满足要求的路径。

输入格式

第一行包含两个以空格分隔的整数 $R$ 和 $C$，分别表示网格的行数和列数。

接下来 $R$ 行，每行包含 $C$ 个不含空格的字符。字符含义如下：

• . 表示该格子可以通过；
• * 表示该格子布满岩石，无法通过。

输出格式

输出若干行，每行包含两个以空格分隔的整数，表示路径依次经过的格子坐标。

第一行必须为 $1\ 1$，最后一行必须为 $R\ C$。路径中任意两个连续坐标所表示的格子必须在上、下、左、右方向上相邻。

样例输入

5 8
..*...**
*.*.*.**
*...*...
*.*.*.*.
....*.*.

样例输出

1 1
1 2
2 2
3 2
3 3
3 4
2 4
1 4
1 5
1 6
2 6
3 6
3 7
3 8
4 8
5 8

数据范围

• $1\le R\le 113$；
• $1\le C\le 77$。

来源与许可

本题为 USACO 2006 October 试题「Cows on Skates」，题面与测试数据整理自 BZOJ。

样例 1

输入

5 8
..*...**
*.*.*.**
*...*...
*.*.*.*.
....*.*.

输出

1 1
1 2
2 2
3 2
3 3
3 4
2 4
1 4
1 5
1 6
2 6
3 6
3 7
3 8
4 8
5 8