2516: 【普及-】【P1605】迷宫
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：15
解决：6
题目描述
给定一个 方格的迷宫，迷宫里有 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
输入
第一行为三个正整数 ，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 ， 代表起点坐标， 代表终点坐标。
接下来 行，每行两个正整数，表示障碍点的坐标。
输出
输出从起点坐标到终点坐标的方案总数。
样例输入 复制
2 2 1
1 1 2 2
1 2样例输出 复制
1提示
对于 的数据，，，，。
#include<bits/stdc++.h>
using namespace std;
int maze[10][10]={0},n,m,t,sx,sy,fx,fy,ans=0;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void dfs(int x,int y) {
if (x==fx && y==fy) {
ans++;
return;
}
for(int i=0;i<4;i++) {
if(maze[x+dx[i]][y+dy[i]]==1) {
maze[x+dx[i]][y+dy[i]] =0;
dfs(x+dx[i],y+dy[i]);
maze[x+dx[i]][y+dy[i]] =1;
}
}
}
int main(){
int x,y;
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
maze[i][j]=1;
}
}
for(int i=0;i<t;i++) {
cin>>x>>y;
maze[x][y]=0;
}
maze[sx][sy]=0;
dfs(sx,sy);
cout<<ans;
return 0;
}