题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

题目描述
无

输入格式
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。
2 2 1
1 1 2 2
1 2

输出格式
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。
1

题解

点击查看
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>

using namespace std;

const int N = 10;

int sum;
int g[N][N];
bool st[N][N];
int n, m, t;
int sx, sy, fx, fy;

void dfs(int x, int y){
	if(x == fx && y == fy){
		sum ++;
		return;
	}
	int dx[] = {1, 0, 0, -1};
	int dy[] = {0, 1, -1, 0};
	for(int i = 0; i < 4; ++i){
		if(g[x + dx[i]][y + dy[i]] == 1 && !st[x + dx[i]][y + dy[i]]){
			st[x][y] = true;
			dfs(x + dx[i], y + dy[i]);
			st[x][y] = false;
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m >> t;
	cin >> sx >> sy >> fx >> fy;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			g[i][j] = 1;
		}
	}
	
	while(t--){
		int x, y;
		cin >> x >> y;
		g[x][y] = -1;
	}
	
	dfs(sx, sy);

	cout << sum << endl;
	
	return 0;
}