AtCoder Beginner Contest 407 D

https://atcoder.jp/contests/abc407/tasks/abc407_d

2進数をベクトルと考えて一次独立のものだけ選べばいいと思ったのですが、HWが20以下だからしらみつぶしで十分ですね。左上からそのマスを飛ばすか横のドミノを置くか縦のドミノを置くかの状態遷移すればよいです。

// Domino Covering XOR
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Table ////////////////////

type Point = usize;
type State = (Point, i64, usize);

struct Table {
    H: usize,
    W: usize,
    A: Vec<Vec<i64>>
}

impl Table {
    fn N(&self) -> usize {
        return self.H * self.W
    }
    
    fn value(&self, pt: Point) -> i64 {
        self.A[pt/self.W][pt%self.W]
    }
    
    fn all_XOR(&self) -> i64 {
        (0..self.N()).fold(0, |x, y| x ^ self.value(y))
    }
    
    fn is_available(&self, pt: Point, filled: usize) -> bool {
        pt < self.N() && ((filled >> (pt as u32)) & 1) == 0
    }
    
    fn nexts(&self, s0: State) -> Vec<State> {
        let (pt0, n0, filled0) = s0;
        if pt0 >= self.N() - 1 {
            return vec![]
        }
        
        let mut states: Vec<State> = vec![(pt0 + 1, n0, filled0)];
        if !self.is_available(pt0, filled0) {
            return states
        }
        if self.is_available(pt0 + 1, filled0) && pt0 % self.W < self.W - 1 {
            // 横のドミノ
            let pt1 = pt0 + 1;
            let n = n0 ^ self.value(pt0) ^ self.value(pt1);
            let filled = filled0 | (1 << pt0) | (1 << (pt1));
            states.push((pt0 + 2, n, filled))
        }
        if self.is_available(pt0 + self.W, filled0) &&
                                    pt0 / self.W < self.H - 1 {
            // 縦のドミノ
            let pt1 = pt0 + self.W;
            let n = n0 ^ self.value(pt0) ^ self.value(pt1);
            let filled = filled0 | (1 << pt0) | (1 << (pt1));
            states.push((pt0 + 1, n, filled))
        }
        return states;
    }
    
    fn read() -> Table {
        let v: Vec<usize> = read_vec();
        let (H, W) = (v[0], v[1]);
        let A: Vec<Vec<i64>> = (0..H).map(|_| read_vec::<i64>()).collect();
        Table { H, W, A }
    }
}


//////////////////// process ////////////////////

use std::cmp::max;

fn F(table: Table) -> i64 {
    let mut max_value = table.all_XOR();
    let mut stack: Vec<State> = vec![(0, table.all_XOR(), 0)];
    while let Some(s0) = stack.pop() {
        for s in table.nexts(s0) {
            max_value = max(s.1, max_value);
            stack.push(s)
        }
    }
    max_value
}

fn main() {
    let table = Table::read();
    println!("{}", F(table))
}