AOJ : 1059 - Mysterious Onslaught

AOJ 動的計画法

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1059&lang=jp
日本語の問題文なので説明省略です.
みょんみょん

アルゴリズム

bitDPを行いました.
左上の1になっているマスを0にするように, みょんを行います.
これを何回か行えば, 必ず全てのマスが0になることがわかります.
この操作を再帰で書いて, メモ化しました.


マップの状態は, ビットで持つようにしました.
高々25ビットなので, これであらわせます.
みょんの操作もXORを行うだけになるので, 非常に書きやすいです.

類題

  • AOJ 0131
    • 左上からという発想が似ている

プログラム

#define MAX 999999999

int n;                      //マップの大きさ
int xorMemo[5][5][5][5][5]; //みょんの操作用
short dp[5][1<<25];         //メモ化用

int solve(int bit){
  if(bit == 0) return 0;
  if(dp[n-1][bit] != -1) return dp[n-1][bit];

  //1になっている左上の座標を探す
  int li,lj;
  for(li=0;li<n;li++){
    for(lj=0;lj<n;lj++){
      if((bit & (1<<(n*li+lj))) != 0){
        break;
      }
    }
    if(lj != n) break;
  }

  //[li][lj]から右下に伸びる長方形でみょんを行う
  int res = MAX;
  REP(hi,li,n){
    REP(hj,lj,n){
      int next = (bit ^ xorMemo[n-1][li][lj][hi][hj]);
      res = min(res,solve(next)+1);
    }
  }

  return dp[n-1][bit]=res;
}

int main(){
  //みょんをXOR操作で行うためのビットを全て生成
  memset(xorMemo,0,sizeof(xorMemo));
  REP(m,1,6){
    rep(li,m){
      rep(lj,m){
        REP(hi,li,m){
          REP(hj,lj,m){
            REP(i,li,hi+1){
              REP(j,lj,hj+1){
                xorMemo[m-1][li][lj][hi][hj] |= (1<<(i*m+j));
              }
            }
          }
        }
      }
    }
  }

  memset(dp,-1,sizeof(dp));
  while(cin>>n,n){
    int bit = 0;
    rep(i,n){
      rep(j,n){
        int x;
        cin>>x;

        if(x == 1){
          bit |= (1<<(i*n+j));
        }
      }
    }

    int ans = solve(bit);
    rep(i,ans) cout<<"myon";
    cout<<endl;
  }
}