/ OIer TK / 题库 /

土地开发的期待

土地开发的期待

测试数据来自 system/1681

背景

"我晕...我刚才以为你们是骗我的呢...这个还真能占岛啊.."

是啊...这个世界上并不是所有的土地都是安静的.......
这些四季都漂浮在海面上的岛屿..也许从地球诞生的那一天开始就没有人类涉足过...

描述

我们用一个m*n的矩阵来描述它的地形...
用0表示岩石.木桩...海岸盐碱地等等障碍物.....、
用1来表示可以耕作的土壤..

然后是x0,y0...是出发地点..你荷着锄头从..这里开始开垦...
不可以碰到石头...也不可以经过已经开垦过的土地..*
不过最后可以在任意一个格子停止...

我们的输出的结果应该最多可以开垦的土地块数...
最好还可以把路径也给打印出来...

格式

输入格式

第一行是两个整数,分别代表m,n(m,n<=5)
以下n行,每行m个字符,用来描述岛屿的特征
其中'0'代表石头,'*'代表开垦过的土地,'S'代表起始位置。
注:小岛左上角的坐标为(1,1)

输出格式

第一行,一个整数max,即从起始点开始最多能开垦的土地的块数。
第二行....没有内容
以下max行,每行以(x,y)的格式,按开垦顺序依次输出要开垦的土地的坐标...
如果有多种线路,输出字典顺序最靠先的一条

样例1

样例输入1

3 3
S11
111
111

样例输出1

9

(1,1)
(1,2)
(1,3)
(2,3)
(2,2)
(2,1)
(3,1)
(3,2)
(3,3)

限制

1s

提示

出发点的土地也是可以开垦的额...
对于100%的数据..m,n小于等于5...
...
如果有多种路径...按道理说..应该任意输出一种都行的...
但那个要写SpecialJudge....但我不会写...所以就麻烦一下输出字典序最小的啦...

(*这里有两种说法了..还有一种说法是..可以经过开垦过的土地..
但是这块开垦过土地就被毁坏掉了....后面这个问题会复杂多少..?.)

"花园里花儿香呀.....laalla.."
"遍地是牛羊> <...."

来源

Usaco Training

信息

ID
1648
难度
(无)
分类
搜索 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者