poj 1048 Follow My Logic-技术圈

Follow My Logic

Description

For this problem you will determine the output of a logic circuit composed of one or more inputs, zero or more dual-input AND/OR gates, and one output. The input circuits are drawn with standard ASCII characters. Circuit paths are represented using horizontal and vertical lines, and junctions. Horizontal lines are represented with dash characters (ASCII code 45 decimal), vertical lines with vertical bar characters (ASCII code 124 decimal), and junctions with plus characters (ASCII code 43 decimal). Inputs are represented using the capital letters A through Z, and the output is represented by a question mark. AND and OR gates are represented as shown in the leftmost entries in the figure below, and their orientation will always be exactly as shown. The location of the gate inputs and output is shown by the middle figure below. Finally, gate inputs or its output can be inverted, represented by a lowercase "oh"character (ASCII code 111 decimal) at the input or output location. The figure on the right below shows a simple but complete logic circuit.

Input

Circuits in the input will obey the following guidelines:
1. The maximum size of the circuit picture is 100 by 100 characters.
2. A path always travels in a straight line unless altered by a junction. At a junction, the path can and will make a ninety degree turn. Two junctions will not be horizontally or vertically adjacent.
3. No paths will be "broken" That is, every path character is guaranteed to be adjacent on both sides to either another path character of the same type, a junction, a gate input, a gate output, a logic input, or the logic output.
4. Circuit paths do not cross or intersect other paths.
5. Gate inputs always approach horizontally from the left as shown above. Gate outputs always leave horizontally to the right as shown above.
6. Inversions may only appear immediately adjacent to a gate input or output, and will always be preceded (in the case of an input) or followed (in the case of an output) by at least one dash as shown above.
The end of a logic diagram in the input is indicated by line containing only a single asterisk in the first column. Following this are several lines which indicate the state of the inputs in the logic diagram. Each of these lines is a string of twenty-six "0"(zero) or "1"characters, with the first position representing the state of input A, the second position representing the state of input B, etc. Note that input values which are not actually used in the circuit may simply be ignored. The list of input states is terminated by a line containing only a single asterisk character in the first column.
Following the asterisk which terminates the list of input states is another circuit diagram followed by a list of input states, which is then followed by another circuit diagram and list of input states, and so on until the end of the file. The file will always contain at least one circuit and one set of inputs for that circuit.

Output

The program is to report the value of the output (0 or 1) of each logic circuit, one value per line, for each set of input values in the list which follows the circuit. The list of outputs for each circuit should be separated by a single blank line.

Sample Input

A---:\
    : )---?
B---:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
A---+
    |    
    +---:\
        : >o---:\
    +---:/     : )---?
    |      C--o:/
B---+
*
00000000000000000000000000
11100000000000000000000000
*

Sample Output

按照我的逻辑

时限： 1000MS		内存限制： 10000K
提交总数： 2469		接受： 679

描述

对于此问题，您将确定由一个或多个输入、零个或多个双输入 AND/OR 门和一个输出组成的逻辑电路的输出。输入电路是用标准 ASCII 字符绘制的。电路路径使用水平线和垂直线以及连接点表示。水平线用破折号表示（ASCII 码 45 十进制），垂直线用竖线表示（ASCII 码 124 十进制），连接处用加号（ASCII 码 43 十进制）表示。输入用大写字母 A 到 Z 表示，输出用问号表示。AND 和 OR 门如下图最左边的条目所示，它们的方向将始终与所示完全相同。门输入和输出的位置如下中图所示。最后，门输入或其输出可以反转，在输入或输出位置由小写“oh”字符（ASCII 代码 111 十进制）表示。下右图显示了一个简单但完整的逻辑电路。

输入

输入中的电路将遵循以下准则：
1. 电路图片的最大尺寸为 100 x 100 个字符。
2. 除非被交叉路口改变，否则路径总是沿直线行进。在交叉路口，小路可以并且将会转九十度。两个交汇点不会水平或垂直相邻。
3. 没有路径会被“破坏” 也就是说，每个路径字符都保证在两侧与另一个相同类型的路径字符、结点、门输入、门输出、逻辑输入或逻辑输出。
4. 电路路径不与其他路径交叉或相交。
5. 门输入总是从左侧水平接近，如上所示。如上所示，门输出始终水平向右。
6. 反转可能只出现在紧邻门输入或输出的位置，并且总是在（在输入的情况下）或在（在输出的情况下）之前至少有一个破折号，如上所示。
输入中逻辑图的结尾由第一列中仅包含一个星号的行表示。在这之后是几行，它们指示逻辑图中输入的状态。这些行中的每一行都是一个由 26 个“0”（零）或“1”字符组成的字符串，第一个位置代表输入 A 的状态，第二个位置代表输入 B 的状态，等等。注意输入值电路中没有实际使用的可能会被忽略。输入状态列表以第一列中仅包含一个星号字符的行终止。
在终止输入状态列表的星号之后是另一个电路图，然后是输入状态列表，然后是另一个电路图和输入状态列表，依此类推，直到文件结束。该文件将始终包含至少一个电路和该电路的一组输入。

输出

该程序将报告每个逻辑电路的输出值（0 或 1），每行一个值，用于电路后面的列表中的每组输入值。每个电路的输出列表应由单个空行分隔。

Sample Input

A---:\
    : )---?
B---:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
A---+
    |    
    +---:\
        : >o---:\
    +---:/     : )---?
    |      C--o:/
B---+
*
00000000000000000000000000
11100000000000000000000000
*

Sample Output

解题思路：

首先读入整幅电路图，找到电路图输出的位置，然后递归分析电路图的逻辑结构，构造一颗逻辑树。然后对于每个输入状态根据逻辑树去递归求值即可。但是要注意电路图中线路方向的处理问题，因为图并非一定是规矩的沿从左至方向，线路可能弯折。比如下面的例子：

A-+
  |
  o:\
   : )-?
B--:/

A---+
    |    
    +---:\
        : >o---:\
    +---:/     : )---?
    |      C--o:/
    +---+
        |
B-------+

代码：

#include 
#include 

using namespace std;

char circuit[105][105];
int h;
int x, y;

enum DIR {
    LEFT, UP, RIGHT, DOWN
};

struct Node {
    int type;    //0-25表示对应输入状态的序号(A-Z); -2 and; -3 or; -4 not.
    int left_child;
    int right_child;
};

Node tree[400];
int tree_len;

char input[27];

bool ReadCircuit() {
    memset(circuit, 0, sizeof(circuit));
    if (!gets(circuit[0])) return false;
    h = 1;
    while (gets(circuit[h++])) {
        if (circuit[h - 1][0] == '*') {
            --h;
            break;
        }
    }
    return true;
}

void FindOutput() {
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < 100; ++j) {
            if (circuit[i][j] == '\0') break;
            if (circuit[i][j] == '?') {
                x = i;
                y = j;
                return;
            }
        }
    }
}

void ConstructTree(int x, int y, int node_id, DIR dir) {
    switch (circuit[x][y]) {
        case '?':
            if (circuit[x][y - 1] == '-') ConstructTree(x, y - 2, node_id, LEFT);
            else if (circuit[x][y + 1] == '-') ConstructTree(x, y + 2, node_id, RIGHT);
            else if (circuit[x - 1][y] == '|') ConstructTree(x - 2, y, node_id, UP);
            else if (circuit[x + 1][y] == '|') ConstructTree(x + 2, y, node_id, DOWN);
            else ConstructTree(x, y - 1, node_id, LEFT);
            break;
        case ')':
            tree[node_id].type = -2;    //and
            tree[node_id].left_child = ++tree_len;
            tree[node_id].right_child = ++tree_len;
            ConstructTree(x - 1, y - 3, tree[node_id].left_child, LEFT);
            ConstructTree(x + 1, y - 3, tree[node_id].right_child, LEFT);
            break;
        case '>':
            tree[node_id].type = -3;    //or
            tree[node_id].left_child = ++tree_len;
            tree[node_id].right_child = ++tree_len;
            ConstructTree(x - 1, y - 3, tree[node_id].left_child, LEFT);
            ConstructTree(x + 1, y - 3, tree[node_id].right_child, LEFT);
            break;
        case 'o':
            tree[node_id].type = -4;    //not
            tree[node_id].left_child = ++tree_len;
            tree[node_id].right_child = -1;
            if (circuit[x][y - 1] == ')' || circuit[x][y - 1] == '>')
                ConstructTree(x, y - 1, tree[node_id].left_child, LEFT);
            else if (circuit[x][y - 1] == '-' && dir != RIGHT)
                ConstructTree(x, y - 2, tree[node_id].left_child, LEFT);
            else if (circuit[x][y + 1] == '-' && dir != LEFT)
                ConstructTree(x, y - 2, tree[node_id].left_child, RIGHT);
            else if (circuit[x - 1][y] == '|' && dir != DOWN)
                ConstructTree(x - 2, y, tree[node_id].left_child, UP);
            else ConstructTree(x + 2, y, tree[node_id].left_child, DOWN);
            break;
        case '+':
            if (dir == UP || dir == DOWN) {
                if (circuit[x][y - 1] == '-') ConstructTree(x, y - 2, node_id, LEFT);
                else ConstructTree(x, y + 2, node_id, RIGHT);
            } else {
                if (circuit[x - 1][y] == '|')ConstructTree(x - 2, y, node_id, UP);
                else ConstructTree(x + 2, y, node_id, DOWN);
            }
            break;
        case '-':
            if (dir == LEFT) ConstructTree(x, y - 1, node_id, LEFT);
            else ConstructTree(x, y + 1, node_id, RIGHT);
            break;
        case '|':
            if (dir == UP) ConstructTree(x - 1, y, node_id, UP);
            else ConstructTree(x + 1, y, node_id, DOWN);
            break;
        default:
            tree[node_id].left_child = -1;
            tree[node_id].right_child = -1;
            tree[node_id].type = circuit[x][y] - 'A';
    }
}

bool GetInput() {
    scanf("%s", input);
    if (input[0] == '*') return false;
    return true;
}

int GetOutput(int i) {
    switch (tree[i].type) {
        case -2:    //and
            return GetOutput(tree[i].left_child) && GetOutput(tree[i].right_child);
        case -3:    //or
            return GetOutput(tree[i].left_child) || GetOutput(tree[i].right_child);
        case -4:    //not
            return !GetOutput(tree[i].left_child);
        default:
            return input[tree[i].type] - '0';
    }
}

int main(){
    while (ReadCircuit()){
        FindOutput();
        tree_len = 0;
        ConstructTree(x, y, 0, LEFT);
        while (GetInput()) {
            printf("%d\n", GetOutput(0));
        }
        printf("\n");
    }
    return 0;
}