题目描述:
本题使用 Special Judge。
Farmer John 把农场划分为了一个 r 行 c 列的矩阵,并发现奶牛们无法通过其中一些区域。此刻,Bessie 位于坐标为 (1,1) 的区域,并想到坐标为 (r,c) 的牛棚享用晚餐。她知道,以她所在的区域为起点,每次移动至相邻的四个区域之一,总有一些路径可以到达牛棚。
这样的路径可能有无数种,请你输出任意一种,并保证所需移动次数不超过 100000。
输入格式:
第一行两个整数 r,c。
接下来 r 行,每行 c 个字符,表示 Bessie 能否通过相应位置的区域。字符只可能是 . 或 *。
. 表示 Bessie 可以通过该区域。
* 表示 Bessie 无法通过该区域。
输出格式:
若干行,每行包含两个用空格隔开的整数,表示 Bessie 依次通过的区域的坐标。
显然,输出的第一行是 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
AC Code:
#include<bits/stdc++.h> using namespace std; #define N 115 char a[N][N];//存入地图的数组 bool vis[N][N];//标记数组 int r,c,flag; int placex[100001],placey[100001];//记录每走一步对应的横纵坐标 int dx[]={0,0,1,-1};//定义两个方向数组 int dy[]={1,-1,0,0}; bool judge(int x,int y) { if(x>=1&&x<=r&&y>=1&&y<=c&&!vis[x][y]&&a[x][y]!='*') { //不越界,这个点没有走过,也不是围墙 return true; } return false; } void dfs(int x,int y,int step) { placex[step]=x;//这个点的横坐标存入此数组 placey[step]=y;//这个点的纵坐标存入此数组 vis[x][y]=1;//这个点标记为1,已经走过 if(x==r&&y==c) {//走到终点 for(int i=1;i<=step;i++) {//循环将所有步数对应的坐标输出 printf("%d %d\n",placex[i],placey[i]); } } for(int i=0;i<4;i++) {//四个方向搜索 int tx=x+dx[i]; int ty=y+dy[i]; if(judge(tx,ty)) {//判断该点是否符合下一步的要求 dfs(tx,ty,step+1);//继续下一个点的搜索,步数加1 } } } int main() { scanf("%d %d",&r,&c); for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) { scanf(" %c",&a[i][j]);//%前面的空格确保地图可以完整输入 } } dfs(1,1,1);//从第一个点(1,1)进入迷宫,步数为第一步 return 0; }