22.3.12走迷宫（dfs，打印路径）

题目描述

有一个n*m格的迷宫(表示有n行、m列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这n*m个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。
请统一用 左上右下的顺序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)

输入

第一行是两个数n，m( 1 < n ， m < 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)->(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)
(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)->(3,5)->(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)->(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)->(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)->(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)

#include<iostream>
#include<stdio.h>
using namespace std;
int n,m;
int a[20][20],book[20][20],step[1000][3];
int x1,y1,x2,y2,k=1,flag=0;
void p(int c)//打印步骤 
{
	for(int i=1;i<=c-1;i++)
	{
		printf("(%d,%d)->",step[i][1],step[i][2]);
	}
	printf("(%d,%d)",x2,y2);
	printf("\n");
	flag++;//是否有路 
}
void dfs(int x,int y)
{
	book[x][y]=1;
	int tx[4]={0,-1,0,1};
	int ty[4]={-1,0,1,0};
	if(x==x2&&y==y2)
	{
		p(k);
		return;
	}
	for(int i=0;i<4;i++)
	{
		int dx=x+tx[i],dy=y+ty[i];
		if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&book[dx][dy]==0&&a[dx][dy]==1)
		{
			book[dx][dy]=1;
			step[k][1]=x;//记录步骤 
			step[k][2]=y;
			k++;//走了多少步 
			dfs(dx,dy);
			k--;
			book[dx][dy]=0;
		}
	}
	return;
}

int main()
{
	cin>>n>>m;
	int i ,j;
	for(i=1;i<=n;i++)//n行m列 
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>x1>>y1;
	cin>>x2>>y2;
	dfs(x1,y1);
	if(flag==0)
	printf("-1\n");

	return 0;
}