解題區/解題區 - UVa

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
*/