[ABC#015] C問題完答までの道程

abc015c.cs

// 2014/11/23 11:16:20
// AC: 24, WA: 0
// http://abc015.contest.atcoder.jp/submissions/283939
// 敗因: n = 1のときの場合分け不足
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class C1
{
    int[,] map;
    int n;
    int k;
    int[] now;

    bool Solve()
    {
        string[] str = Console.ReadLine().Split(' ');
        n = int.Parse(str[0]);
        k = int.Parse(str[1]);

        map = new int[n, k];
        now = new int[n];

        for (int i = 0; i < n; i++)
        {
            string[] s = Console.ReadLine().Split(' ');
            for (int j = 0; j < k; j++)
                map[i, j] = int.Parse(s[j]);
        }
        if (n == 1)
        {
            for (int i = 0; i < k; i++)
                if (map[0, i] == 0) return true;

            return false;
        }
        else
            return Check(0, 0);
    }

    bool Check(int q, int index)
    {
        if (q < n - 1)
        {
            for (int i = 0; i < k; i++)
            {
                now[q] = i;
                if (Check(q + 1, 0)) return true;
            }
            return false;
        }

        int last = map[0, now[0]];
        for (int i = 1; i < q; i++)
            last = last ^ map[i, now[i]];

        for (int i = 0; i < k; i++)
            if ((last ^ map[q, i]) == 0)
                return true;

        return false;
    }

    static void Main(string[] args)
    {
        Console.WriteLine(new C1().Solve() ? "Found" : "Nothing");
        Console.ReadLine();
    }
}