首页 > 代码库 > SDUT 1269-走迷宫(DFS打印路径)
SDUT 1269-走迷宫(DFS打印路径)
走迷宫
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打印路径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。