P1605 迷宫

题目背景

迷宫【问题描述】

给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和

终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫

中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

输入样例输出样例

【数据规模】

1≤N,M≤5

题目描述

输入输出格式

输入格式：

【输入】

第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点

坐标FX,FY。接下来T行，每行为障碍点的坐标。

输出格式：

【输出】

给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方

案总数。

输入输出样例

输入样例#1：

2 2 1
1 1 2 2
1 2

输出样例#1：

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 using namespace std;
 8 bool a[10][10],vis[10][10];
 9 int ans;
10 int n,m,t;
11 int sx,sy,ex,ey;
12 inline int read()
13 {
14     int t=0,f=1;
15     char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)){t=t*10+ch-'0';ch=getchar();}
18     return t*f;
19 } 
20 void bfs(int x,int y)
21 {
22     if(x==ex && y==ey) {ans++;return ;}
23     if(x<1 || x>n || y<1 || y>m || a[x][y] || vis[x][y]) return ;
24     vis[x][y]=1;
25     bfs(x-1,y);
26     bfs(x+1,y);
27     bfs(x,y-1);
28     bfs(x,y+1);
29     vis[x][y]=0;
30 }
31 
32 int main()
33 {
34     n=read();m=read();t=read();
35     //cout<<n<<" "<<m<<" "<<t<<endl;
36     sx=read();sy=read();
37     ex=read();ey=read();
38     for(int i=1;i<=t;i++)
39     {
40         int x,y;
41         x=read();y=read();
42         a[x][y]=1;
43     }
44     if(a[ex][ey]) {printf("0");return 0;}
45     bfs(sx,sy);
46     printf("%d",ans);
47     return 0;
48 }

P1605

bfs模板