1688: 【例】【基础】迷宫的所有路径
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：14
解决：8
题目描述
已知一N×N的迷宫，允许往上、下、左、右四个方向行走，且迷宫中没有任何障碍，所有的点都可以走。
现请你按照右、下、左、上顺序进行搜索，找出从左上角到右下角的所有路径。
输入
输入一个整数N（N<=5）代表迷宫的大小。
输出
按右、下、左、上搜索顺序探索迷宫，输出从左上角1,1点走到右下角N,N点的所有可能的路径。
样例输入 复制
3样例输出 复制
1:1,1->1,2->1,3->2,3->3,3
2:1,1->1,2->1,3->2,3->2,2->3,2->3,3
3:1,1->1,2->1,3->2,3->2,2->2,1->3,1->3,2->3,3
4:1,1->1,2->2,2->2,3->3,3
5:1,1->1,2->2,2->3,2->3,3
6:1,1->1,2->2,2->2,1->3,1->3,2->3,3
7:1,1->2,1->2,2->2,3->3,3
8:1,1->2,1->2,2->3,2->3,3
9:1,1->2,1->2,2->1,2->1,3->2,3->3,3
10:1,1->2,1->3,1->3,2->3,3
11:1,1->2,1->3,1->3,2->2,2->2,3->3,3
12:1,1->2,1->3,1->3,2->2,2->1,2->1,3->2,3->3,3提示
#include<bits/stdc++.h>
using namespace std;
#define N 110
char a[N][N];
int d[N][N];
bool vis[N][N];
int n,c,r[N][3];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int sx,sy,ex,ey;
void print(int k){
c++;
cout<<c<<':';
for(int i=1;i<k;i++){
cout<<r[i][1]<<','<<r[i][2]<<"->";
}
cout<<n<<","<<n<<endl;
}
void dfs(int x,int y,int k){
r[k][1]=x;
r[k][2]=y;
if(x==n&&y==n){
print(k);
return;
}
int tx,ty;
for(int i=1;i<=4;i++){
tx=x+dx[i];
ty=y+dy[i];
if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&vis[tx][ty]==false){
vis[tx][ty]=true;
dfs(tx,ty,k+1);
vis[tx][ty]=false;
}
}
}
int main(){
cin>>n;
r[1][1]=1;
r[1][2]=1;
vis[1][1]=true;
dfs(1,1,1);
return 0;
}