【蓝桥杯每日一题】与或异或——DFS

与或异或

题目描述

小蓝有一张门电路的逻辑图，如下图所示： 图中每个三角形代表着一种门电路，可能是与门、或门、异或门中的任何一种，它接受上一层中的两个圆形中的数据作为输入，产生一个输出值输出到 下一级 (如图中箭头所示)。图中圆形表示的是暂存的输出结果，取值只可能是 0 或 1，为了便于表示我们用 $arr[i][j]$ 表示第 $i(0\le i\le 4)$ 行第 $j(0\le j\le i)$ 个圆形的值。其中 $arr[0]=(In[0],In[1],In[2],In[3],In[4])$ 表示的是输入数据，对于某个 $arr[i][j](i\ge 0)$，计算方式为 $arr[i][j]=arr[i-1][j]oparr[i-1][j+1]$，其中 $op$ 表示的是将 $arr[i-1][j]$、$arr[i-1][j+1]$ 作为输入，将 $arr[i][j]$ 作为输出的那个门电路，与门、或门、异或门分别对应于按位与 &、按位或 $(|)$ 、按位异或(^)运算符。 现在已知输入为 $In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1$，小蓝想要使得最终的输出 $Out$ 的值为 1，请问一共有多少种不同的门电路组合方式？其中上图中显示的就是一种合法的方式。

解题思路

那这道题就是通过遍历来找出所能够满足条件的方法，首先具体怎么遍历，就是先通过每一遍历运算符的操作，然而每遍历一次操作，就要判断是否要换行，是否要结束递归，更新到下一个操作之后就有要进行操作符的遍历。

Accepted

#include <iostream>
using namespace std;
int res = 0;
int arr[6][10]  = {{1,0,1,0,1}};
void dfs(int r,int c,int k) {
    if(k == 1) {
        arr[r][c] = arr[r-1][c] | arr[r-1][c+1];
    } 
    if(k == 2) {
        arr[r][c] = arr[r-1][c] ^ arr[r-1][c+1];
    }
    if(k == 3) {
        arr[r][c] = arr[r-1][c] & arr[r-1][c+1];
    }

    // 判断结束条件
    if(r == 4 && c == 0) {
        if(arr[r][c] == 1) {
            res ++;
        }
        return ;
    }

    // 当前行结束
    if(r + c == 4) {
        r++;
        c = 0;
    } else c++;

    for(int i = 1;i <= 3;i++) {
        dfs(r,c,i);
    }
}

int main()
{
    int op[3] = {1,2,3};
    
    for(int k = 1;k <= 3;k++){
      dfs(1,0,k);
    }
    cout<<res<<endl;
    return 0;
}