UVa 12051 - Mazes in Higher Dimensions

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

好比 2D 方格,從左下角到右上角的方法數。而這一題是在三維空間,一樣的方式要越來越靠近右上方的頂點,但是部分點會有障礙物,會造成無法通行。

題目給定的維度事實上是終點座標,而非該維度數,用 row major 的時候要計算 dim[i]+1

Sample Input

1
2
3
4
5
6
7
8
3 0
5 5 5
3 1
9 8 7
1 1 1
0 0

Sample Output

1
2
Case 1: 756756
Case 2: 6318655200

Solution

特地用懶標記完成 dp 計算,但是忘了有可能無法抵達終點,忘了補上最對於終點的懶標記操作,直接輸出 dp[ret] 結果一直噴 WA。

懶標記檢查 if (used[ret] != testcase) dp[ret] = 0;

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXN 3000005
long long dp[MAXN] = {};
int used[MAXN] = {}, ob[MAXN] = {}; // obstacle
int main() {
memset(dp, 0, sizeof(dp));
memset(ob, 0, sizeof(ob));
memset(used, 0, sizeof(used));
int n, m, dim[16], row[16], v[16];
int testcase = 0, cases = 0;
while (scanf("%d %d", &n, &m) == 2 && n+m) {
for (int i = 0; i < n; i++) {
scanf("%d", &dim[i]);
dim[i]++;
}
testcase++;
row[n - 1] = 1;
for (int i = n - 2; i >= 0; i--)
row[i] = row[i+1] * dim[i+1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
scanf("%d", &v[j]);
int x = 0;
for (int j = 0; j < n; j++)
x += v[j] * row[j];
ob[x] = testcase;
}
if(ob[0] == testcase){
printf("Case %d: 0\n", ++cases);
continue;
}
int ret = 0;
for (int i = 0; i < n; i++)
ret += (dim[i] - 1) * row[i];
queue<int> Q;
Q.push(0), used[0] = testcase;
dp[0] = 1;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
long long ways = dp[x];
for (int i = 0; i < n; i++)
v[i] = x / row[i], x %= row[i];
for (int i = 0; i < n; i++) {
v[i]++;
if (v[i] < dim[i]) {
x = 0;
for (int j = 0; j < n; j++)
x += v[j] * row[j];
if (ob[x] != testcase) {
if (used[x] != testcase)
dp[x] = 0;
dp[x] += ways;
if (used[x] != testcase)
Q.push(x), used[x] = testcase;
}
}
v[i]--;
}
}
if (used[ret] != testcase) dp[ret] = 0;
printf("Case %d: %lld\n", ++cases, dp[ret]);
}
return 0;
}
/*
3 0
5 5 5
3 1
9 8 7
1 1 1
3 2
9 8 7
1 1 1
5 6 6
3 2
9 8 7
2 3 4
9 8 7
3 2
9 8 7
2 3 4
9 8 7
0 0
*/