q023.rs

use std::collections::HashMap;
use proconio::{input, marker::Chars};

const MOD: u32 = 1_000_000_007;

fn main() {
  input! { h: usize, w: usize, c: [Chars; h], };
  let mut dp = HashMap::with_capacity(200000);
  dp.insert(0u32, 1u32);
  for i in 0..h {
    let mut dp1 = HashMap::with_capacity(200000);
    std::mem::swap(&mut dp, &mut dp1);
    for (key, val) in dp1 {
      let key = (key & !(1<<w)) << 1;
      *dp.entry(key).or_insert(0) += val;
    }
    for j in 0..w {
      let mut dp1 = HashMap::with_capacity(200000);
      std::mem::swap(&mut dp, &mut dp1);
      for (key, val) in dp1 {
        let val = val % MOD;
        let key0 = key & !(1<<j);
        *dp.entry(key0).or_insert(0) += val;
        if key & 0b1111 << j >> 1 != 0 || c[i][j] != '.' { continue; }
        let key1 = key | (1<<j);
        dp.insert(key1, val);
      }
    }
  }
  let mut ans = 0;
  for (_, val) in dp {
    ans = (ans + val) % MOD;
  }
  println!("{}", ans);
}

q023_with_comments.rs

// (i,j)の通り数を求めるためにそれより前のw+1マスでbitDP。下位ビットから順に
// (i,0),(i,1),..,(i,j-1),(i-1,j-1),(i-1,j),(i-1,j+1),..,(i-1,w-1) でw+1ビット。
// 1マス更新したあとは
// (i,0),(i,1),..,(i,j-1),(i,j),(i-1,j),(i-1,j+1),..,(i-1,w-1) の順にする。
// HashMap: key -> valで管理する。
// 更新前(i-1,j-1)に置いていない状態をkey0, 置いている状態をkey1として対で扱う。
// key0もkey1も新しい(i, j)に0は置ける。
// 1がおけるのは(i,j-1),(i-1,j-1),(i-1,j),(i-1,j+1)の4ビットが0のときのみ。

use std::collections::HashMap;
use proconio::{input, marker::Chars};

const MOD: u32 = 1_000_000_007;

fn main() {
  input! { h: usize, w: usize, c: [Chars; h], };
  // 組み合せ数は最大で160000程度。new()だとリアロケートで2秒ほど遅くなる。
  let mut dp = HashMap::with_capacity(200000);
  // (0, 0)に遷移する前はキングを全く置かない状態1通りのみ
  dp.insert(0u32, 1u32);
  for i in 0..h {
    // 行が変わる際のbitを更新
    let mut dp1 = HashMap::with_capacity(200000);
    std::mem::swap(&mut dp, &mut dp1);
    for (key, val) in dp1 {
      let key = (key & !(1<<w)) << 1;
      *dp.entry(key).or_insert(0) += val;
    }
    for j in 0..w {
      let mut dp1 = HashMap::with_capacity(200000);
      std::mem::swap(&mut dp, &mut dp1);
      for (key, val) in dp1 {
        let val = val % MOD;
        // いずれの状態からも(i,j)に0を置くことはできる
        let key0 = key & !(1<<j);
        *dp.entry(key0).or_insert(0) += val;
        // 周囲に1がある場合は(i,j)に1が置けないのでここで終了
        if key & 0b1111 << j >> 1 != 0 || c[i][j] != '.' { continue; }
        // (i,j)に1がおけるので加算。key == key1 の場合は上ですでに弾かれている
        let key1 = key | (1<<j);
        dp.insert(key1, val);
      }
    }
  }
  let mut ans = 0;
  for (_, val) in dp {
    ans = (ans + val) % MOD;
  }
  println!("{}", ans);
}