7. 走迷宫
XJOI - 题目ID：1226必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 2000ms
空间限制: 262144kB
题目描述
时间限制：2s 空间限制：256M
描述
给定一个迷宫。在迷宫中有一些障碍物无法通过，请计算出从左上角到右下角的移动方案总数。（一个位置不能经过两次，只能上下左右四个方向走）
输入格式
第一行包含两个整数n，m，表示迷宫的大小。1 <= N，M<= 6
接下来的n行，每行包含m个字符，代表迷宫。
＃代表障碍
*代表你可以去的位置
左上角和右下角用“*”表示
输出格式
一个整数。
样本输入1
5 6 *****# #### #### #### ******
样本输出1
2
样本输入2
6 6 ****** ****** ****** ****** ****** ******
示例输出2
1262816
提示
我的代码：
#include<iostream>
using namespace std;
int n,m;
char a[10][10];
bool vis[10][10];
int fx[]={-1,1,0,0};
int fy[]={0,0,-1,1};
int sum=0;
void dfs(int x,int y){
if(x==n&&y==m){
sum++;
return ;
}
for(int i=0;i<4;i++){
int tx=x+fx[i];
int ty=y+fy[i];
if(vis[tx][ty]==0&&tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]!='#'){
vis[tx][ty]=1;
dfs(tx,ty);
vis[tx][ty]=0;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
dfs(1,1);
cout<<sum;
return 0;
}