山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 015 C - 高橋くんのバグ探し

深さ優先探索

C - 高橋くんのバグ探し

全探索をする問題で、深さ優先探索を利用して解くことができます。

コード

import java.util.Scanner;

public class ProblemC1 {
    static int[][] T;
    static int N;
    static int K;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        K = scan.nextInt();
        T = new int[N][K];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < K; j++) {
                T[i][j] = scan.nextInt();
            }
        }
        scan.close();
        if(dfs(0, 0)){
            System.out.println("Found");
        }else {
            System.out.println("Nothing");
        }

    }
    public static boolean dfs(int d, int t) {
        if(d == N) {
            if(t == 0) {
                return true;
            }
            return false;
        }
        for(int i = 0; i < K; i++) {
            if(dfs(d + 1, t ^ T[d][i])) {
                return true;
            }
        }
        return false;
    }
}
````