解題區/解題區 - UVa

UVa 738 - A Logical Problem

contents

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

Problem

給予 AND, OR, NOT 結合的電路圖，保證最多 26 個變數，分別由大寫字母表示，接著對於每一組詢問輸出電路結果。

Sample Input

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
A-:\
  : )-?
B-:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
  +-A
  |
  +-:\
    : >o-:\
  +-:/   : )-?
  |+----o:/
B-+|
 C-+
*
00000000000000000000000000
11100000000000000000000000
*
A-:\
  : )-?
A-:/
*
00000000000000000000000000
10000000000000000000000000
*

Sample Output

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

Solution

不想轉化成 graph，那麼就直接針對盤面做遞迴分析，特別要記錄之前的方向位置，以免電路接錯路徑。而題目沒有說明 ? 銜接的方向，有可能四個方向都有。一開始沒有注意到這個問題，導致刷了很多 RE。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 512
char g[MAXN][MAXN], val[MAXN];
int n;
int validPos(int x, int y) {
    return x >= 0 && x < MAXN && y >= 0 && y < MAXN;
}
int query(int x, int y, int dir, char pre) {
    if (g[x][y] == '?')
        return query(x, y - 1, 2, '?');
    if (g[x][y] >= 'A' && g[x][y] <= 'Z')
        return val[g[x][y] - 'A'] - '0';
    if (g[x][y] == 'o')
        return !query(x, y - 1, 2, 'o');
    if (g[x][y] == ')')
        return query(x - 1, y - 3, 2, ')') && query(x + 1, y - 3, 2, ')');
    if (g[x][y] == '>')
        return query(x - 1, y - 3, 2, '>') || query(x + 1, y - 3, 2, '>');
    if (g[x][y] == '-') {
        if (dir == 2)
            return query(x, y - 1, 2, '-');
        if (dir == 3)
            return query(x, y + 1, 3, '-');
        assert(false);
    }
    if (g[x][y] == '|') {
        if (dir == 0)
            return query(x - 1, y, 0, '|');
        if (dir == 1)
            return query(x + 1, y, 1, '|');
        assert(false);
    }
    if (g[x][y] == '+') {
        if (dir != 1 && validPos(x-1, y) && g[x-1][y] == '|')
            return query(x - 1, y, 0, '|');
        if (dir != 0 && validPos(x+1, y) && g[x+1][y] == '|')
            return query(x + 1, y, 1, '|');
        if (dir != 3 && validPos(x, y-1) && g[x][y-1] == '-')
            return query(x, y - 1, 2, '-');
        if (dir != 2 && validPos(x, y+1) && g[x][y+1] == '-')
            return query(x, y + 1, 3, '-');
        assert(false);
    }
    assert(g[x][y] == ' ' && pre != '?');
    return 0;
}
int main() {
    memset(g, ' ', sizeof(g));
    while (gets(g[0])) {
        int qx = -1, qy = -1;
        for (n = 1; gets(g[n]) && g[n][0] != '*'; n++);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < MAXN; j++) {
                if (g[i][j] == '?') {
                    qx = i, qy = j;
                }
            }
        }
        
        int dir = -1;
        if (validPos(qx-1, qy) && g[qx-1][qy] == '|')
        	qx--, dir = 0;
        else if (validPos(qx+1, qy) && g[qx+1][qy] == '|') 
        	qx++, dir = 1;
        else if (validPos(qx, qy-1) && g[qx][qy-1] == '-') 
        	qy--, dir = 2;
        else if (validPos(qx, qy+1) && g[qx][qy+1] == '-') 
        	qy++, dir = 3;
        assert(qx >= 0 && qy >= 0);
        while (scanf("%s", val) == 1 && val[0] != '*')
            printf("%d\n", query(qx, qy, dir, '?'));
        puts("");
        memset(g, ' ', sizeof(g));
        while (getchar() != '\n');
    }
    return 0;
}
/*
A-:\
  : )-?
B-:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
  +-A
  |
  +-:\
    : >o-:\
  +-:/   : )-?
  |+----o:/
B-+|
 C-+
*
00000000000000000000000000
11100000000000000000000000
*
A-:\
  : )-?
A-:/
*
00000000000000000000000000
10000000000000000000000000
*
A-o:\
   : )o-?
A-o:/
*
00000000000000000000000000
10000000000000000000000000
*
        ? 
A-o:\   | 
   : )o-+
A-o:/
*
00000000000000000000000000
10000000000000000000000000
*
 */