1017: 【深度优先搜索】TOM挖金矿

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:3 解决:2

题目描述

TOM得到了一张迷宫一样的古老地图,据说这是一张金矿图,他计划一个人悄悄得带上工具和袋子按照地图得提示去挖金矿。
出发前他必须规划好怎么样能找遍地图上的各个可能有金矿的地点。
地图如下:
3 5
000**
00*00
0*0*0
地图终0表示可以走,*表示是坚固的岩石壁,TOM计划按照顺时针的方式尝试4个方向:上->右->下->左来挖每个矿点是否有金矿,矿区入口在坐标(1,1)即第一行第一列

输入

第一行n,m两个正整数(2<=n,m<=1000)
      接下来n行,每行m个字符(0或*)组成。

输出

按照TOM计划的顺序输出他所找的所有矿点的坐标

样例输入 复制

3 5
000**
00*00
0*0*0

样例输出 复制

1 1
1 2
1 3
2 2
2 1
3 1