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

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(1m,n15)m,n(1m,n15)接下来是m mm行n nn列由1 11和0 00组成的数据最后两行是起始点和结束点。输出格式所有可行的路径描述一个点时用( x , y ) (x,y)(x,y)的形式除开始点外其他的都要用-表示方向。如果没有一条可行的路则输出− 1 -1−1。输入输出样例 #1输入 #15 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 nm14nm14且每个位置都是1 11的话有69450664761521361664274701548907358996488 6945066476152136166427470154890735899648869450664761521361664274701548907358996488种路径。解题思路本题核心是深度优先搜索(DFS)用于枚举迷宫中从起点到终点的所有无重复合法路径。迷宫尺寸小于15 × 15 15×1515×15完全适配DFS暴力搜索。首先按照题目要求定义左、上、右、下的固定搜索方向保证路径顺序合规用二维数组标记已走过的格子避免路径重复从起点开始递归探索四个方向每移动一步就拼接路径字符串当到达终点时直接输出完整路径。设置标记变量记录是否存在有效路径若DFS结束后未找到任何路径输出− 1 -1−1。算法严格遵循题目规则完整输出所有满足条件的路径。总结核心逻辑DFS按指定方向遍历迷宫搜索所有无重复点的起点到终点路径。关键操作方向数组左上右下、访问标记去重、路径动态拼接、终点判断输出。效率保障小尺寸迷宫下DFS能快速遍历所有路径完美满足题目输出要求。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;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(sxtxsyty){coutpendl;f1;return;}ll dir[4][2]{{0,-1},{-1,0},{0,1},{1,0}};for(ll i0;i4;i){ll xsxdir[i][0],ysydir[i][1];if(g[x][y]1v[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);cinnm;for(ll i1;in;i)for(ll j1;jm;j)cing[i][j];cinsxsytxty;v[sx][sy]1;dfs(sx,sy,(cc[sx],cc[sy]));if(!f)cout-1endl;return0;}