想要算出各個輸出端口的延遲，就要先得出其前一個端口的延遲。
想要得出輸出端口的狀態，就要先得出其前一個端口的狀態。
把這寫遞迴式就可以了。
我的寫法:
先定義一個結構，儲存電閥的各項資訊
struct vr
{
int in1 = 0;//輸入端口1
int in2 = 0;//輸入端口2
short boool = -1;//這個電閥輸出
short aoxn = 0;//這個邏輯閥的種類，輸入端口與輸出端口不會用到此參數
int delay = -10;//電閥的延遲
};
//先宣告一下等一下要用到的函式，使用傳參考呼叫，可以直接修改陣列元素。
vr* pfrs = nullptr;//因為懶得將指標作為函式的引數之一，乾脆宣告成全域變數
short check_boool(vr& fr);//檢查電閥的狀態
int check_delay(vr& fr);//檢查電閥的延遲
將各項輸入儲存進vector<vr>中，從索引值1至(p+q+r)，陣列第一項(索引值為0)保留不使用。(這樣比較方便存取)
int p, q, r, m;
cin >> p >> q >> r >> m;
vector<vr> frs(p + q + r + 1);
frs[0].delay = -1;//陣列第一項將是計算延遲時遞迴的終點。
for (int i = 1; i < p + 1; ++i) {
cin >> frs[i].boool;
frs[i].delay = -1;//輸入端口的延遲視為-1
}
int u, v;
for (int i = p + 1; i < p + q + 1; ++i) {
cin >> frs[i].aoxn;//輸入各個邏輯閥的種類
}
for (int i = 0; i < m; ++i) {
cin >> u >> v;
if (frs[v].in1 == 0) {
frs[v].in1 = u;//電閥的輸入端口1
}
else {
frs[v].in2 = u;//電閥的輸入端口2
}
}
pfrs = frs.data();//將全域變數pfrs指向vector<vr> frs的第一個元素，以便在函式中使用
準備工作完成，可以開始寫遞迴用的函式喽!
int check_delay(vr& fr)接受一個指向vr結構的參考，並回傳該電閥的延遲
int check_delay(vr& fr) {
//如果delay成員不是預設值(-1)，代表已計算過此電閥的延遲，直接回傳delay就可以了
if (fr.delay != -10) {
return fr.delay;
}
//否則計算此電閥的延遲，為兩個輸入電閥中的延遲較大者再加一
fr.delay = max(check_delay(pfrs[fr.in1]), check_delay(pfrs[fr.in2])) + 1;
return fr.delay;
}
不用擔心只有1個輸入的電閥(輸出端口與NOT 閘)，它們的第二的輸入端口指向了vector<vr> frs的第1個元素(索引值0)，該元素已保留不使用。
short check_boool(vr& fr)接受一個指向vr結構的參考，並回傳該電閥的輸出
short check_boool(vr& fr) {
//如果boool成員不是 -1 (預設值)，代表已計算過此電閥的輸出，直接回傳boool就可以了
if (fr.boool != -1) {
return fr.boool;
}
//否則根據電閥種類進行遞迴，判斷此電閥的輸出
switch (fr.aoxn) {
case 0://輸出端口
fr.boool = check_boool(pfrs[fr.in1]);
return fr.boool;
case 1://AND 閘
fr.boool = check_boool(pfrs[fr.in1]) and check_boool(pfrs[fr.in2]) ? 1 : 0;
return fr.boool;
case 2://OR 閘
fr.boool = check_boool(pfrs[fr.in1]) or check_boool(pfrs[fr.in2]) ? 1 : 0;
return fr.boool;
case 3://XOR 閘
fr.boool = check_boool(pfrs[fr.in1]) xor check_boool(pfrs[fr.in2]) ? 1 : 0;
return fr.boool;
case 4://NOT 閘
fr.boool = !check_boool(pfrs[fr.in1]) ? 1 : 0;
return fr.boool;
}
}
回到main()函式，只要針對每個輸出閥呼叫check_delay與check_boool就可以了。
int Max=0;
for (int i = p + q + 1; i < p + q + r + 1; ++i) {
Max = Max > check_delay(frs[i]) ? Max : frs[i].delay;
}
cout << Max << '\n';
for (int i = p + q + 1; i < p + q + r + 1; ++i) {
cout<<check_boool(frs[i])<<' ';
}
還是把完整程式碼附上好了。
#include<iostream>#include<vector>#include<cmath>using namespace std;struct vr{int in1 = 0;//輸入端口1的索引int in2 = 0;//輸入端口2的索引short boool = -1;//這個電閥輸出short aoxn = 0;//這個邏輯閥的種類，輸入端口與輸出端口不會用到此參數int delay = -10;//電閥的延遲};vr* pfrs = nullptr;//因為懶得將指標作為函式的引數之一，乾脆宣告成全域變數short check_boool(vr& fr);//檢查電閥的狀態int check_delay(vr& fr);//檢查電閥的延遲int main() {ios::sync_with_stdio(false);cin.tie(0);int p, q, r, m;cin >> p >> q >> r >> m;vector<vr> frs(p + q + r + 1);frs[0].delay = -1;//陣列第一項將是計算延遲時遞迴的終點。for (int i = 1; i < p + 1; ++i) {cin >> frs[i].boool;frs[i].delay = -1;//輸入端口的延遲視為-1}int u, v;for (int i = p + 1; i < p + q + 1; ++i) {cin >> frs[i].aoxn;//輸入各個邏輯閥的種類}for (int i = 0; i < m; ++i) {cin >> u >> v;if (frs[v].in1 == 0) {frs[v].in1 = u;//電閥的輸入端口1}else {frs[v].in2 = u;//電閥的輸入端口2}}pfrs = frs.data();//將全域變數pfrs指向vector<vr> frs的第一個元素，以便在函式中使用int Max=0;for (int i = p + q + 1; i < p + q + r + 1; ++i) {Max = Max > check_delay(frs[i]) ? Max : frs[i].delay;}cout << Max << '\n';for (int i = p + q + 1; i < p + q + r + 1; ++i) {cout<<check_boool(frs[i])<<' ';}}int check_delay(vr& fr) {//回傳該電閥的延遲//如果delay成員不是預設值(-1)，代表已計算過此電閥的延遲，直接回傳delay就可以了if (fr.delay != -10) {return fr.delay;}//否則計算此電閥的延遲，為兩個輸入電閥中的延遲較大者再加一fr.delay = max(check_delay(pfrs[fr.in1]), check_delay(pfrs[fr.in2])) + 1;return fr.delay;}short check_boool(vr& fr) {//回傳該電閥的輸出//如果boool成員不是 -1 (預設值)，代表已計算過此電閥的輸出，直接回傳boool就可以了if (fr.boool != -1) {return fr.boool;}//否則根據電閥種類進行遞迴，判斷此電閥的輸出switch (fr.aoxn) {case 0://輸出端口fr.boool = check_boool(pfrs[fr.in1]);return fr.boool;case 1://AND 閘fr.boool = check_boool(pfrs[fr.in1]) and check_boool(pfrs[fr.in2]) ? 1 : 0;return fr.boool;case 2://OR 閘fr.boool = check_boool(pfrs[fr.in1]) or check_boool(pfrs[fr.in2]) ? 1 : 0;return fr.boool;case 3://XOR 閘fr.boool = check_boool(pfrs[fr.in1]) xor check_boool(pfrs[fr.in2]) ? 1 : 0;return fr.boool;case 4://NOT 閘fr.boool = !check_boool(pfrs[fr.in1]) ? 1 : 0;return fr.boool;}}