题目描述

有一个 m×n 格的迷宫(表示有 m 行、n 列)，其中有可走的也有不可走的，如果用 11 表示可以走，00 表示不可以走。

文件读入这 m×n 个数据和起 始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。

现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应 信息(用-l表示无路)。

输入格式

第一行是两个数 m，n(1< m，n <15)，接下来是 m 行 n 列由 1 和 0 组成的数据，最后两行是起始点和结束点。

输出格式

所有可行的路径，描述一个点时用 (x，y)的形式，除开始点外，其他的都要用 “一>” 表示方向。 如果没有一条可行的路则输出 -1 。

样例

样例输入

5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

样例输出

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

来源

搜索

#include<bits/stdc++.h>
using namespace std;
int m,n,a[20][20],endx,endy;
bool no=true;
int dx[4]={0,-1,1,0},dy[4]={-1,0,0,1};
struct Route{int x,y;
}route[5001];
void DFS(int x,int y,int num){if(x==endx&&y==endy){for(int i=0;i<num;i++){cout<<"("<<route[i].x<<","<<route[i].y<<")->";}cout<<"("<<x<<","<<y<<")"<<endl;no=false;return;}route[num].x=x,route[num].y=y;for(int i=0;i<4;i++){if(a[x+dx[i]][y+dy[i]]==1 && 1<=x+dx[i]<=m && 1<=y+dy[i]<=n){a[x][y]=0;DFS(x+dx[i],y+dy[i],num+1);a[x][y]=1;}}
}
int main(){while(cin>>m>>n){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}int sx,sy;cin>>sx>>sy;cin>>endx>>endy;DFS(sx,sy,0);if(no) printf("-1\n");}return 0;
}