蓝桥杯算法提高VIP-开灯游戏-题解dfs（Java代码）

解题思路:

            数据存放：

            使用二维数组Switch来存放每个开关能控制的灯的编号，_Switch数组存放每个开关的开关状态，light数组存放每个灯的状态。

            算法思路：

            使用dfs，每次下探时决定当前开关是关闭还是开启，即_Switch数组当前位是'0'还是'1'，每当排好一种就检查这个开关序列是否合乎要求，即这样操作后是否只有四个灯亮。

注意事项:   

            1、light[Switch[i][j] - 1] = 0;  此处的减一不能忘了。

            2、Arrays.fill(light, 0);  这一步也很重要，每次检查完要将其初始化。

参考代码:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static int[][] Switch = new int[][] {	//存储每个开关能控制的灯的编号
		{2,4},
		{1,3,5},
		{2,6},
		{1,5,7},
		{2,4,6,8},
		{3,5,9},
		{4,8},
		{5,7,9},
		{6,8}
	};
	public static int[] light = {0,0,0,0,0,0,0,0,0};	//灯的状态
	
	public static void dfs(char[] _Switch, int cur) {
		//考虑好了一种开关序列，检查是否合乎要求（即操作后是否只有四个灯亮）
		if(cur == 9)
		{
			if(check(_Switch))
			{
				System.out.println(String.valueOf(_Switch));
			}
			return;
		}
		
		//不开
		_Switch[cur] = '0';
		dfs(_Switch, cur + 1);
		
		//开
		_Switch[cur] = '1';
		dfs(_Switch, cur + 1);
	}
	
	public static boolean check(char[] _Switch) {    //操作后是否只有四个灯亮
		int sum = 0;
		for(int i = 0; i < 9; i++)
		{
			if(_Switch[i] == '1')
			{
				for(int j = 0; j < Switch[i].length; j++)
				{
					if(light[Switch[i][j] - 1] == 1)
					{
						light[Switch[i][j] - 1] = 0;
						//从关变成了开，所以开着的灯+1
						sum--;
					}
					else
					{
						light[Switch[i][j] - 1] = 1;
						//从开变成了关，所以开着的灯-1
						sum++;
					}
				}
			}
		}
		Arrays.fill(light, 0);
		return sum == 4;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		char[] _Switch = "000000000".toCharArray();	//开关的状态
		dfs(_Switch, 0);
		
		in.close();
	}
}