题解
【提高】迷宫的路径
1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n,m,p; char c[50][50]; bool a[50][50]; int r[50][3]; int fx[5]={0,0,1,0,-1}; int fy[5]={0,1,0,-1,0}; bool direct=false; void print(int k) { direct=true; p++; cout<<p<<":"; for(int i=1;i<k;i++) { cout<<r[i][1]<<","<<r[i][2]<<"->"; } cout<<r[k][1]<<","<<r[k][2]<<endl; } void dfs(int k) { //使用k型 int tx,ty; for(int i=1;i<5;i++) { tx=r[k-1][1]+fx[i]; ty=r[k-1][2]+fy[i]; if(tx>0&&ty>0&&tx<=n&&ty<=m&&c[tx][ty]=='o'&&a[tx][ty]==false) { a[tx][ty]=true; r[k][1]=tx; r[k][2]=ty; if(tx==n&&ty==m) { print(k); } else { dfs(k+1); }//递进 a[tx][ty]=false; } } } int main() { cin>>n>>m; getchar(); r[1][1]=1; r[1][2]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>c[i][j]; } } a[1][1]=true; dfs(2); if(direct==false) cout<<"no"<<endl; }
- 1