首页 > 代码库 > SDUT 1269-走迷宫（DFS打印路径）

SDUT 1269-走迷宫（DFS打印路径）

2024-07-30 17:52:33   223人阅读

走迷宫

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)
path[]数组保存路径。。无脑dfs 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
struct node
{
	int x,y;
}path[1000];
int n,m,sx,sy,ex,ey,ok,step;
bool vis[16][16],ma[16][16];
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
void print()
{
	for(int i=0;i<step-1;i++)
		printf("(%d,%d)->",path[i].x,path[i].y);
	printf("(%d,%d)\n",ex,ey);
}
void dfs(int x,int y)
{
	if(x==ex&&y==ey)
	{
		ok=1;
		print();
		return ;
	}
	for(int i=0;i<4;i++)
	{
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(tx>=1&&tx<=m&&ty>=1&&ty<=n&&!vis[tx][ty]&&ma[tx][ty])
		{
			path[step].x=tx;
			path[step++].y=ty;
			vis[tx][ty]=1;
			dfs(tx,ty);
			vis[tx][ty]=0;
			step--;
		}
	}
}
int main()
{
	while(~scanf("%d%d",&m,&n))
	{
		ok=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++)
			scanf("%d",&ma[i][j]);
		scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
		vis[sx][sy]=1;step=0;
		path[step].x=sx;path[step++].y=sy;
		dfs(sx,sy);
		if(!ok)
			puts("-1");
	}
	return 0;
}

SDUT 1269-走迷宫（DFS打印路径）


联系
我们