跳到主要内容

P6207 [USACO06OCT] Cows on Skates G

[USACO06OCT] Cows on Skates G P6207​

本题使用 Special Judge。

Farmer John 把农场划分为了一个 rr 行 cc 列的矩阵，并发现奶牛们无法通过其中一些区域。此刻，Bessie 位于坐标为 (1,1)(1,1) 的区域，并想到坐标为 (r,c)(r,c) 的牛棚享用晚餐。她知道，以她所在的区域为起点，每次移动至相邻的四个区域之一，总有一些路径可以到达牛棚。

这样的路径可能有无数种，请你输出任意一种，并保证所需移动次数不超过 100000100000。

输入数据格式​

第一行两个整数 r,cr,c。

接下来 rr 行，每行 cc 个字符，表示 Bessie 能否通过相应位置的区域。字符只可能是 . 或 *。

  • . 表示 Bessie 可以通过该区域。
  • * 表示 Bessie 无法通过该区域。

输出数据格式​

若干行，每行包含两个用空格隔开的整数，表示 Bessie 依次通过的区域的坐标。

显然，输出的第一行是 1 1 ，最后一行是 r c。

相邻的两个坐标所表示的区域必须相邻。

输入输出样例​

输入 #1输出 #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

说明与提示​

【数据范围】

对于 100%100\% 的数据，1≤r≤1131\le r\le 113，1≤c≤771\le c\le 77。

*【样例说明】 *

图为样例输出的示意图。答案不唯一。

*练习笔记​

暂无人完成练习，做第一个完成练习的人—-first blood ！