https://www.luogu.org/problem/P1605
从起点到终点有多少种不同的方案
1 // luogu-judger-enable-o2 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 #include <cmath> 6 #include <queue> 7 #include <vector> 8 #include <cstring> 9 #include <map> 10 #define mem(a) memset(a,0,sizeof(a)) 11 using namespace std; 12 typedef long long lll; 13 const int maxn = 200005; 14 const lll INF = 0x3f3f3f3f3f; 15 int vis[6][6],vis2[6][6],ans; 16 int dir[8][2]= {0,1,0,-1,1,0,-1,0,-1,-1,1,-1,-1,1,1,1}; 17 int dir2[4][2]= {0,1,0,-1,1,0,-1,0}; 18 bool flag; 19 int n,m,t,ex,ey,sx,sy; 20 void dfs(int x,int y) 21 { 22 if(x == ex&&y == ey) 23 { 24 ans++; 25 return ; 26 } 27 else 28 { 29 for(int i=0; i<4; i++) 30 { 31 int fx = x + dir2[i][0],fy = y + dir2[i][1]; 32 if(fx>=1&&fx<=n&&fy>=1&&fy<=m&&vis[fx][fy]==0&&vis2[fx][fy]==0) 33 { 34 vis2[x][y]=1; 35 dfs(fx,fy); 36 vis2[x][y]=0; 37 } 38 } 39 } 40 } 41 int main() 42 { 43 cin >> n >> m >> t; 44 45 cin >> sx >> sy >> ex >> ey; 46 mem(vis); 47 mem(vis2); 48 int x,y; 49 for(int i=0; i<t; i++) 50 { 51 cin >> x >> y; 52 vis[x][y] = 1; 53 } 54 if(vis[ex][ey] == 1) 55 { 56 cout << "0" << endl; 57 } 58 else{ 59 dfs(sx,sy); 60 cout << ans << endl; 61 } 62 return 0; 63 }