走迷宫
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
有一个m*n格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，输入这m*n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-1表示无路）。
输入
第一行是两个数m，n（1< m, n< 15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
输出
所有可行的路径，输出时按照左上右下的顺序。描述一个点时用（x，y）的形式，除开始点外，其他的都要用“->”表示。如果没有一条可行的路则输出-1。
示例输入
5 4 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 5 4
示例输出
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4) (1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4) (1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4) (1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4) (1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4) (1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
解题思路：
这道题就是一个简单的模板DFS，只要利用递归的思路不停的往下走就可以了，关于路径的打印，这里巧妙的利用了一个path数组，把x和y分别压进去，然后通过step来不断的调整path的值，在这个过程中同样需要应该有的回溯，才能输出随后的所有路径，其中step作为全局变量是非常重要的，以前一直不会输出路径，如今get了这个新技能，，，，
QAQ~
# include<cstdio>
# include<iostream>
# include<cstring>
using namespace std;
# define MAX 1000
int m,n;
int step;//$重要$,从起点到终点的所有路上上的节点的个数和
int grid[16][16];
int vis[16][16];
int stx,sty;
int edx,edy;
int flag;
int next[4][2] ={{-1,0},{0,-1},{0,1},{1,0}};
struct node
{
int x;
int y;
}path[MAX];
void output()
{
for ( int i = 0;i < step-1;i++ )
printf("(%d,%d)->",path[i].x,path[i].y);
printf("(%d,%d)\n",edx,edy);
}
void dfs( int x,int y )
{
if ( x==edx && y==edy )
{
flag = 1;
output();
return;
}
for ( int i = 0;i < 4;i++ )
{
int n_x = x+next[i][0];
int n_y = y+next[i][1];
if( n_x>=1&&n_x<=m&&n_y>=1&&n_y<=n&&!vis[n_x][n_y]&&grid[n_x][n_y] )
{
path[step].x = n_x;
path[step++].y = n_y;
vis[n_x][n_y] = 1;
dfs( n_x,n_y );
vis[n_x][n_y] = 0;
step--;
}
}
}
int main(void)
{
while ( cin>>m>>n )
{
flag = 0;
memset( path,-1,sizeof(path) );
memset( vis,0,sizeof(vis) );
for ( int i = 1;i <= m;i++ )
{
for ( int j = 1;j <= n;j++ )
{
cin>>grid[i][j];
}
}
cin>>stx>>sty;
cin>>edx>>edy;
vis[stx][sty] = 1;
step = 0;
path[step].x = stx;
path[step++].y = sty;
dfs( stx,sty );
if ( !flag )
{
cout<<"-1"<<endl;
}
}
return 0;
}
代码；