AOJ 1270 : Manhattan Wiring

問題リンク : Manhattan Wiring | Aizu Online Judge

問題概要 :
h * w の表に'2'と'3'がそれぞれ２つずつ存在する
その他は'0'か'1'である
'2'と'2'を、'3'と'3'を線で繋ぎたい
ただし、それらの線同士が交差してはいけない
線の長さの和が最小となるように繋いだときのその長さを出力せよ
条件を満たした上で繋げない場合は 0 と出力すること

解法 :
良くある1行覚えるタイプのDPそのまま
プラグDP？
1行の状態をビットでもって、各マスに対して状態を更新していく
今回は2と2,3と3を繋がなければならないため線分が2から伸びているものなのか3から伸びているものなのか覚えておく必要がある
そのため、2ビットで１つの辺を表すようにする
00 -> その辺をまたぐ線はない
01 -> その辺を2から伸びている線がまたぐ
10 -> その辺を3から伸びている線がまたぐ

後は、今みているマスの左と上に合わせて正しいつなぎ方を選び状態を更新すれば良い

正しいつなぎ方は次の画像の通り 見て分かると良いね

今いるマスが障害物の場合、
０のマスの場合
2か3のマスの場合　を考える

以上、
典型なので考えるところはほとんどなかったが実装が酷い
うまいやり方でもあるのだろうか
全て場合分けしてるのは正気の沙汰とは思えない

こういったDPは、不正な状態で更新しないので今みているマスについて正しい処理をするようにすればそれ以外について考えなくてよい
最小を求めるので2,3を含まない線分（ループ等）については考えなくてよい（最小となりえないため）

コード :

#include<bits/stdc++.h>

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

using namespace std;

const int IINF = INT_MAX;
const int MAX_W = 9;
typedef pair<int,int> ii;


int h,w;
int field[10][10],indice[10][10];
int dp[2][1<<((MAX_W+1)*2)];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

inline bool isValid(int x,int y) { return 0 <= x && x < w && 0 <= y && y < h; }

#define SET(bitmask,index,value) ( bitmask = ( ( bitmask & ~(1<<(2*index)) & ~(1<<(2*index+1)) ) | ( value << (index*2) ) ) )
#define GET(bitmask,x) ( ( ( bitmask >> ( 2 * x ) ) & 1 ) | ( ( ( bitmask >> (2*x+1) ) & 1) << 1 ) )
#define FIX(bitmask) ((bitmask<<2)&((1<<(2*(w+1)))-1))
#define STAR ( field[y][x] == 2 || field[y][x] == 3 )
#define update(x,v) ( ( x == -1 ) ? ( x = v ) : ( x = min(x,v) ) )


void compute(){

  vector<int> state;
  rep(bitmask,(1<<((w+1)*2))) {
    bool success = true;
    for(int i=0;i<(w+1)*2;i+=2) if( ( ( bitmask >> i ) & 1 ) && ( ( bitmask >> (i+1) ) & 1 ) ) { success = false; break; }
    if( success ) state.push_back(bitmask);
  }
  memset(dp,-1,sizeof(dp));

  int _size = state.size();
  bool initter = true, phase = false;
  int mini = IINF;
  int encounter = 0;
  rep(y,h){
    rep(x,w){

      if( field[y][x] == 2 || field[y][x] == 3 ) ++encounter;
      if( initter ) dp[phase][0] = 0;

      rep(i,_size){
        int bitmask = state[i];

        if( dp[phase][bitmask] == -1 ) continue;
        if( dp[phase][bitmask] >= mini ) continue;

        // 障害物
        if( field[y][x] == 1 ) {
          int nbitmask = bitmask;
          SET(nbitmask,x,0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]);
          continue;
        }

        int nbitmask;
        // 0 0
        if( !( ( GET(bitmask,x) == 0 ) && ( GET(bitmask,(x+1)) == 0 ) ) ) goto Label1;
        if( STAR ) {
          // x 0
          if( y+1 < h && field[y+1][x] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,((field[y][x]==3)+1));
            if( x == w-1 ) nbitmask = FIX(nbitmask);
          
            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
          // 0 x
          if( x+1 < w && field[y][x+1] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,(x+1),((field[y][x]==3)+1));

            if( x == w-1 ) nbitmask = FIX(nbitmask);

            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
        } else {
          // x x
          if( x+1 < w && y+1 < h && field[y][x+1] != 1 && field[y+1][x] != 1 ) {
            REP(color,1,3){
              nbitmask = bitmask;
              SET(nbitmask,x,color);
              SET(nbitmask,(x+1),color);
              if( x == w-1 ) nbitmask = FIX(nbitmask);
              update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
            }
          }
          // 0 0
          nbitmask = bitmask;
          SET(nbitmask,x,0);
          SET(nbitmask,(x+1),0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]);
        }

        continue;
      Label1:;
        // x 0
        // 0 x
        int color;
        if( !( ( GET(bitmask,x) && ( GET(bitmask,(x+1)) == 0 ) ) || ( GET(bitmask,(x+1)) && ( GET(bitmask,x) == 0 ) ) ) ) goto Label2;
        color = GET(bitmask,x) | GET(bitmask,(x+1));
        if( STAR ) {
          // 0 0
          if( ((color==1)?2:3) == field[y][x] ) {
            nbitmask = bitmask;
            SET(nbitmask,x,0);
            SET(nbitmask,(x+1),0);
            if( x == w-1 ) nbitmask = FIX(nbitmask);
            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
        } else {
          // x 0
          if( y+1 < h && field[y+1][x] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,color);
            SET(nbitmask,(x+1),0);
            if( x == w-1 ) nbitmask = FIX(nbitmask);


            update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
          }
          
          // 0 x
          if( x+1 < w && field[y][x+1] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,0);
            SET(nbitmask,(x+1),color);

            if( x == w-1 ) nbitmask = FIX(nbitmask);
            update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
          }
        }
        continue;
      Label2:;
        // x x
        if( !( GET(bitmask,x) && GET(bitmask,(x+1)) ) ) goto Label3;
        if( GET(bitmask,x) != GET(bitmask,(x+1)) ) goto Label3;

        color = GET(bitmask,x);
        
        // 0 0
        if( !STAR ) {
          nbitmask = bitmask;
          SET(nbitmask,x,0);
          SET(nbitmask,(x+1),0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
        }
      Label3:;

      }
      if( field[y][x] == 2 || field[y][x] == 3 ) initter = false;
      rep(i,_size) dp[phase][state[i]] = -1;
      if( encounter >= 4 && dp[!phase][0] != -1 ) {
        mini = min(mini,dp[!phase][0]);
      }
      phase = !phase;
    }
  }
  if( dp[phase][0] != -1 ) mini = min(mini,dp[phase][0]);
  if( mini != IINF ) printf("%d\n",mini-2);
  else puts("0");
}

int main(){
  while( scanf("%d %d",&h,&w), h|w ){
    rep(i,h) rep(j,w) scanf("%d",&field[i][j]);
    compute();
  }
  return 0;
}