UVa 12804 - The Necronomicon of Computing

contents

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

Problem

給一段簡單的組合語言,有三種指令。

  1. 判斷指令:有可能跳到第 x 個指令,不然就會執行下一行指令。
  2. 計算指令:計算完,執行下一行指令。
  3. 跳躍指令:直接跳躍到第 x 個指令。

判斷這支程式是否有機會停止、或者是進入無限迴圈、還是一直都會結束。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3
3
A
A
J 1
5
A
J 4
J 5
C 3
A
4
A
A
C 2
A

Sample Output

1
2
3
NEVER
ALWAYS
SOMETIMES

Solution

知道指令與指令之間的關係,不仿建造一個有向圖,判斷使否存在一個環,根據 BFS 若沒有辦法抵達終點,

  • 沒有辦法抵達終點,有環,保證程式會進入無限迴圈。
  • 有辦法抵達終點,有環,有機會停止。
  • 其他-總會停止。
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
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAXN 1024
vector<int> g[MAXN];
char cmd[MAXN][16];
int N[MAXN], used[MAXN], instk[MAXN];
int loopflag, endflag;
void dfs(int u) {
instk[u] = 1, used[u] = 1;
for (int i = 0; i < g[u].size(); i++) {
if (used[g[u][i]] == 0)
dfs(g[u][i]);
if (instk[g[u][i]] == 1)
loopflag = 1;
}
instk[u] = 0;
}
int main() {
int testcase, L;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &L);
for (int i = 0; i <= L + 1; i++)
g[i].clear();
for (int i = 1; i <= L; i++) {
scanf("%s", cmd[i]);
if (cmd[i][0] == 'A') {
g[i].push_back(i+1);
} else if (cmd[i][0] == 'J') {
scanf("%d", &N[i]);
g[i].push_back(N[i]);
} else if (cmd[i][0] == 'C') {
scanf("%d", &N[i]);
g[i].push_back(N[i]);
g[i].push_back(i+1);
}
}
memset(used, 0, sizeof(used));
memset(instk, 0, sizeof(instk));
loopflag = 0, endflag = 0;
dfs(1);
endflag = used[L + 1];
if (loopflag == 0 && endflag == 1)
puts("ALWAYS");
else if (loopflag == 1 && endflag == 0)
puts("NEVER");
else
puts("SOMETIMES");
}
return 0;
}
/*
3
3
A
A
J 1
5
A
J 4
J 5
C 3
A
4
A
A
C 2
A
*/