HDU 1693 : Eat The Trees

問題リンク : Problem - 1693

問題概要:
h*w のグリッドがあり、各マスには木が生えているかなにもないかのどちらかである
化け物が木の生えているマスに現れ、隣接するマスで木が生えているマスに移動しどんどん木を食べて、その後に消える
移動経路が円になるように移動する ( 現れるマスと消えるマスは同じ )
一度移動した後はそのマスの木はなくなるため、2度訪れることはできない
まだ木が残っている場合は再度現れて木を食べる
木の食べ方の移動経路は何通り存在するか？

解法 :
插头DP
日本でいう一行覚えるDPなのだろうか、
プラグを繋いだか繋がないかで1か0を割り当てDP

コード:

#include<iostream>
#include<cstdio>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

int h,w;
int field[20][20];
ll dp[400][1<<15];

void compute(){
  rep(i,h*w+1) rep(j,(1<<(w+1))) dp[i][j] = 0LL;
  dp[0][0] = 1LL;
  
  rep(y,h) rep(x,w) {
    int cur = x + y * w, next = cur + 1;

    rep(bitmask,(1<<(w+1)))if( dp[cur][bitmask] ){

      int left = bitmask & (1<<x);
      int top  = bitmask & (1<<(x+1));

      if( field[y][x] ) {
	if( left && top ) {
	  int rleft = ~(1<<x);
	  int rtop  = ~(1<<(x+1));
	  int nbitmask = ( bitmask & rleft & rtop );
	  if( x == w-1 ) { nbitmask <<= 1; }
	  if( nbitmask <= (1<<(w+1))-1 ) {
	    dp[next][nbitmask] += dp[cur][bitmask];
	  }
	} else if( !left && !top ) {
	  int nbitmask = bitmask | (1<<x) | (1<<(x+1));
	  if( x == w-1 ) { nbitmask <<= 1; }
	  if( nbitmask <= (1<<(w+1))-1 ) {
	    dp[next][nbitmask] += dp[cur][bitmask];
	  }
	} else {
	  int rleft = ~(1<<x);
	  int rtop  = ~(1<<(x+1));
	  int nbitmask = ( bitmask & rleft & rtop );

	  nbitmask |= (1<<x);
	  if( x == w-1 ) { nbitmask <<= 1; }
	  if( nbitmask <= (1<<(w+1))-1 ) {
	    dp[next][nbitmask] += dp[cur][bitmask];
	  }

	  nbitmask = ( bitmask & rleft & rtop );
	  nbitmask |= (1<<(x+1));
	  if( x == w-1 ) { nbitmask <<= 1; }
	  if( nbitmask <= (1<<(w+1))-1 ) {
	    dp[next][nbitmask] += dp[cur][bitmask];
	  }

	}
      } else {
	if( !left && !top ) {
	  int nbitmask = bitmask;
	  if( x == w-1 ) { nbitmask <<= 1;  } 
	  if( nbitmask <= (1<<(w+1))-1 ) {
	    dp[next][nbitmask] += dp[cur][bitmask];
	  }
	}
      }
    }
  }

  cout << dp[h*w][0];
}

int main(){
  int T,CNT = 1;
  cin >> T;
  while( T-- ) {
    cin >> h >> w;
    rep(i,h) rep(j,w) cin >> field[i][j];
    printf("Case %d: There are ",CNT++);
    compute();
    puts(" ways to eat the trees.");
  }
  return 0;
}