激光樣式——第九屆藍橋杯C語言B組（國賽）

原創

標題：激光樣式
x星球的盛大節日為增加氣氛，用30台機光器一字排開，向太空中打出光柱。
安裝調試的時候才發現，不知什麼原因，相鄰的兩台激光器不能同時打開！
國王很想知道，在目前這種bug存在的情況下，一共能打出多少種激光效果？
顯然，如果只有3台機器，一共可以成5種樣式，即：
全都關上（sorry, 此時無聲勝有聲，這也算一種）
開一臺，共3種
開兩台，只1種
30台就不好算了，國王只好請你幫忙了。
要求提交一個整數，表示30台激光器能形成的樣式種數。

註意，只提交一個整數，不要填寫任何多餘的內容。

DFS：

每一臺機器都只有開和關兩種狀態，機器關閉是不需要滿足任何條件的，打開機器需要判斷其左右兩邊是否有機器打開。

在深搜過程中，讓每一臺機器都嘗試關閉/打開這2種狀態，當深搜完最後一臺時，激光樣式+1，回溯。

public class Main{
    static int arr[]=new int[32];
    
    static long total=0L;
    
    static int Judge(int value) {
        if(arr[value-1]==1 || arr[value+1]==1) {
            return 0;    //相鄰的燈有燈開
        }
        return 1;
    }
    
    static void fun(int num) {
        if(num==31) {
            total++;
            return;
        }
        int i=0;
        for(i=0;i<=1;i++) {    //0表示關燈，1表示開燈
            if(i==0) {    //關燈一定可以
                fun(num+1);
            }
            if(i==1) {    //試著開燈
                if(Judge(num)==1) {
                    arr[num]=1;
                    fun(num+1);
                    arr[num]=0;    //回溯
                }
            }
        }
    }
    
    public static void main(String args[]) {
        fun(1);
        System.out.println(total);
    }
    
}

答案：2178309

22:56:15

2018-06-03