1222-EXTENDED LIGHTS OUT

問題（外部リンク）

1222 -- EXTENDED LIGHTS OUT

実装の概要

30マスあるので全てのマスについてボタンを押すかどうかを考えると2^30パターンとなり、それで全部0になったかどうかのチェックも含めると間に合いません。
ですが、一番上の行だけであれば2^6=64パターンなので全パターン試すことができます。
二行目以降は順次「上のマスが1ならそのマスを中心に十字状に反転する」という処理を行えば解くことができます。もし上のマスに1があった場合、後戻りはできないという制約上必ずその1つ下のマスを基準として反転しないと上のマスを最終的に0にできないからです。
64パターンの中で、最終的に全てのマスが0になっていることが確認できればそれが答えです。

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int matrix[][] = new int[5][6];
		
		for(int k = 0; k < n; k++){
			for(int i = 0; i < 5; i++){
				for(int j = 0; j < 6; j++){
					matrix[i][j] = sc.nextInt();
				}
			}
			
			solve(matrix, k + 1);
		}

	}

	static void solve(int[][] mat, int id){
		int matrix[][] = new int[5][6];
		int record[][];
		//極端な話、1行目の返し方を32パターン全て試せば解ける
		for(int i = 0; i <= 63 ; i++){
			//配列をコピーする
			copyMatrix(mat, matrix);
			record = new int[5][6];
			
			//1行目の返し方を決め打ちしてやる
			flipFirstLine(matrix, i, record);
			
			for(int j = 1; j < 5; j++){
				for(int k = 0; k < 6; k++){
					if(matrix[j - 1][k] == 1){
						flipCross(matrix, j, k, record);
					}
				}
			}
			
			if(allTurnedOff(matrix)){
				System.out.println("PUZZLE #"+id);
				showMatrix(record);
				return;
			}
		}
		
		System.out.println("ERROR");
	}
	
	static void copyMatrix(int[][] from, int[][] to){
		for(int j = 0; j < 5 ; j++){
			for(int k = 0; k < 6; k++){
				to[j][k] = from[j][k];
			}
		}
	}
	
	static void showMatrix(int[][] matrix){
		for(int j = 0; j < 5 ; j++){
			for(int k = 0; k < 6; k++){
				System.out.print(matrix[j][k]);
				if(k != 5){
					System.out.print(" ");
				}
			}
			System.out.println();
		}
	}
	
	static boolean allTurnedOff(int[][] mat){
		for(int i = 0; i < mat.length; i++){
			for(int j = 0; j < mat[0].length ; j++){
				if(mat[i][j] == 1){
					return false;
				}
			}
		}
		
		return true;
	}
	static void flipFirstLine(int[][] mat, int seed, int record[][]){
		int[] pow = {1,2,4,8,16,32};
		
		for(int i = 0; i < 6; i++){
			if((seed&pow[i]) != 0){
				flipCross(mat, 0, i, record);
			}
		}
		
	}
	
	static void flipCross(int[][] matrix, int y, int x, int[][] record){
		int h = matrix.length; int w = matrix[0].length;
		
		record[y][x] = 1;
		flip(matrix, y, x);
		if(y != 0){
			flip(matrix, y - 1, x);
		}
		if(y != h - 1){
			flip(matrix, y + 1, x);
		}
		if(x != 0){
			flip(matrix, y, x - 1);
		}
		if(x != w - 1){
			flip(matrix, y, x + 1);
		}
	}
	
	static void flip(int[][] matrix, int y, int x){
		matrix[y][x] = (matrix[y][x] + 1)%2;
	}
}