当前位置：首页 > news >正文

P1238 走迷宫【洛谷算法习题】

news 2026/5/14 6:08:01

P1238 走迷宫

网页链接

P1238 走迷宫

题目描述

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

优先顺序：左上右下。数据保证随机生成。

输入格式

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

输出格式

所有可行的路径，描述一个点时用( x , y ) (x,y)(x,y)的形式，除开始点外，其他的都要用->表示方向。

如果没有一条可行的路则输出− 1 -1−1。

输入输出样例 #1

输入 #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,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)

说明/提示

数据保证随机生成。事实上，如果n = m = 14 n=m=14n=m=14且每个位置都是1 11的话，有69450664761521361664274701548907358996488 6945066476152136166427470154890735899648869450664761521361664274701548907358996488种路径。

解题思路

本题核心是深度优先搜索(DFS)，用于枚举迷宫中从起点到终点的所有无重复合法路径。迷宫尺寸小于15 × 15 15×1515×15，完全适配DFS暴力搜索。首先按照题目要求定义左、上、右、下的固定搜索方向，保证路径顺序合规；用二维数组标记已走过的格子，避免路径重复；从起点开始递归探索四个方向，每移动一步就拼接路径字符串，当到达终点时直接输出完整路径。设置标记变量记录是否存在有效路径，若DFS结束后未找到任何路径，输出− 1 -1−1。算法严格遵循题目规则，完整输出所有满足条件的路径。

总结

核心逻辑：DFS按指定方向遍历迷宫，搜索所有无重复点的起点到终点路径。
关键操作：方向数组（左上右下）、访问标记去重、路径动态拼接、终点判断输出。
效率保障：小尺寸迷宫下，DFS能快速遍历所有路径，完美满足题目输出要求。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll g[17][17],v[17][17],n,m,sx,sy,tx,ty;conststring cc[16]={"0","1","2","3","4","5","6","7","8","9","10","11","12","13","14","15"};boolf;voiddfs(ll sx,ll sy,string p){if(sx==tx&&sy==ty){cout<<p<<endl;f=1;return;}ll dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};for(ll i=0;i<4;i++){ll x=sx+dir[i][0],y=sy+dir[i][1];if(g[x][y]==1&&v[x][y]==0){v[x][y]=v[sx][sy]+1;dfs(x,y,p+"->"+"("+cc[x]+","+cc[y]+")");v[x][y]=0;}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)cin>>g[i][j];cin>>sx>>sy>>tx>>ty;v[sx][sy]=1;dfs(sx,sy,"("+cc[sx]+","+cc[sy]+")");if(!f)cout<<-1<<endl;return0;}