ZeroJudge M933: 邏輯電路

題目敘述

每筆資料第一行有四個正整數P、Q、R、M，下一行會有P個整數 (0或1) 代表輸入端口的數值，接下來會有Q個正整數代表邏輯端的判斷類型 (1 為 AND、2 為 OR、3 為 XOR、4 為 NOT)。最後會有M行，每行有兩個正整數A和B，代表從A點到B點有一條線。點的命名方式可以餐考以下圖片，圖片為範例輸入/輸出 #1的解析圖。

要求輸出延遲的秒數 (會在解題思路中解釋) 和輸出端點的值。

範例輸入 #1

4 5 4 13

1 0 1 0

1 2 3 4 1

1 5

2 5

2 6

3 6

3 7

4 7

4 8

5 10

6 9

6 11

7 9

8 13

9 12

範例輸出 #1

2

0 1 1 1

範例輸入 #2

5 6 4 15

1 1 0 1 0

2 1 3 4 1 3

1 6

2 7

7 13

7 6

3 7

3 8

4 8

5 9

8 10

9 10

10 14

10 11

9 11

6 12

11 15

範例輸出 #2

3

1 0 1 0

解題思路

可以使用一個struct來存取每一個端點/邏輯端的數值，將資料都收到struct中之後，使用BFS先跑輸入端點，將輸入端點的終點值的起點值存成目前的數字。經過判斷已經可以做邏輯端的運算後就可以將運算過後的值放到struct中存輸出值的變數。延遲的部分只需判斷跑了幾次的BFS再-1即可。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <vector>
using namespace std;

struct node
{
    vector<int>from;
    vector<int>to;
    int output = -1;
    int delay = 0;
    int gate = -1;
};

int delay = 0;
vector<node>vec;

void BFS(vector<int>start)
{
    if (start.size() == 0) return;
    delay++;
    vector<int>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        node vv = vec[start[i]];
        for (int j = 0; j<vv.to.size(); j++)
        {
            int to = vv.to[j];
            vec[to].from.push_back(start[i]);
            if ((vec[to].gate == 4 && vec[to].from.size() == 1) || (vec[to].from.size() == 2))
            {
                newStart.push_back(to);
                node point = vec[to];
                int gate = vec[to].gate;
                if (gate == 1)
                {
                    if (vec[point.from[0]].output == 1 && vec[point.from[1]].output == 1)
                    {
                        vec[to].output = 1;
                    }
                    else vec[to].output = 0;
                }
                else if (gate == 2)
                {
                    if (vec[point.from[0]].output == 1 || vec[point.from[1]].output == 1)
                    {
                        vec[to].output = 1;
                    }
                    else vec[to].output = 0;
                }
                else if (gate == 3)
                {
                    if (vec[point.from[0]].output != vec[point.from[1]].output) vec[to].output = 1;
                    else vec[to].output = 0;
                }
                else
                {
                    if (vec[point.from[0]].output == 0) vec[to].output = 1;
                    else vec[to].output = 0;
                }
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int in, out, logic, line;
    cin >> in >> logic >> out >> line;
    vector<int>start;
    for (int i = 0; i<in+out+logic; i++)
    {
        node tmp;
        vec.push_back(tmp);
    }
    for (int i = 0; i<in; i++)
    {
        int tmp;
        cin >> tmp;
        vec[i].output = tmp;
        start.push_back(i);
    }
    for (int i = in; i<in+logic; i++)
    {
        int tmp;
        cin >> tmp;
        vec[i].gate = tmp;
    }
    for (int i = 0; i<line; i++)
    {
        int a, b;
        cin >> a >> b;
        vec[a-1].to.push_back(b-1);
    }
    BFS(start);
    cout << delay-1 << endl;
    for (int i = in+logic; i<in+logic+out; i++)
    {
        cout << vec[vec[i].from[0]].output << " ";
    }
    cout << "\n";
}