P1238 走迷宫

题目描述

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

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

输入格式

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

输出格式

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

如果没有一条可行的路则输出 $-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$ 且每个位置都是 $1$ 的话，有 $69450664761521361664274701548907358996488$ 种路径。

C++实现

#include<bits/stdc++.h>
using namespace std;
int a[17][17],s[17][17],n,m,bx,by,ex,ey;
const string c[16]={“0”,“1”,“2”,“3”,“4”,“5”,“6”,“7”,“8”,“9”,“10”,“11”,“12”,“13”,“14”,“15”};
bool flag;
void dfs(int bx,int by,string ans){
if(bxex&&byey){cout<<ans<<endl;flag=1;}
int d[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
for(int i=0;i<4;i++){
int x=bx+d[i][0],y=by+d[i][1];
if(a[x][y]==1&&s[x][y]==0){
s[x][y]=s[bx][by]+1;//深搜
dfs(x,y,ans+“->”+“(”+c[x]+“,”+c[y]+“)”);
s[x][y]=0;//回溯
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>a[i][j];
cin>>bx>>by>>ex>>ey;s[bx][by]=1;
dfs(bx,by,“(”+c[bx]+“,”+c[by]+“)”);//起点(bx,by)
if(!flag)cout<<-1<<endl;
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容