#2508. 滑旱冰的奶牛

滑旱冰的奶牛

题目描述

经过跟FarmerJohn\red{Farmer John}长达数年的谈判,奶牛们终于如愿以偿地得到了想要的旱冰鞋。

农场上大部分的区域都很平整,适合在上面滑动,但有一些虚的土地上有很多的岩石,凭奶牛们的旱冰技术,是没有办法通过的。 农成以看成一个被划分成R(1<=R<=113)\red{R(1<=R<=113)}C(1<=C<=77)\red{C(1<=C<=77)}列的矩阵。

快要开饭了,贝茜发现自己在坐标为(1,1)\red{(1,1)}的格子里,并且她想赶到坐标为(R,C)\red{(R,C)}的牛棚去享用她的晚饭。贝茜知道,以她所在的格子为起点,每次向上、下、左 、右滑动(但不能沿对角线滑动),一定能找到一条通往牛棚的、不经过任何有大量岩石的格子的路。

请你为她指出任意一条通往牛棚的路径。

输入格式

1\red{1}行: 两个用空格隔开的整数,R\red{R}C\red{C }

2..R+1\red{2..R+1}行: 每行包含C\red{C}个字符(不含空格),

字符只可能是'.'或'\red{*}'。是'.' 的话,表示贝茜能从这个格子里通过,是'\red{*}'的话,则这个格子 是不能通过的多岩石地带

输出格式

1...?\red{1...?}行: 每行包含2\red{2}个用空格隔开的整数,表示贝茜回牛棚路径所通过的格 子的坐标。

输出的第一行显然应该是11\red{1 1,}最后一行是RC\red{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