AOJ : 1174 - 同色パネル結合 (Identically Colored Panels Connection)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1174&lang=jp
日本語の問題文があるので, 説明省略です

アルゴリズム

左上のマスを1〜6に変える処理を再帰で書きます.
ただし, 5回目に色を変えるときだけ入力で与えられたCに変えます.
色を変えたときは, 幅優先でマップを書き変え.
最後にパネルの数をカウントするときも, 幅優先でカウント.

プログラム

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;

int h,w,c;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int area(vvi &v){
  int res = 0;
  int color = v[0][0];
  queue<P> open;
  bool closed[h][w];

  memset(closed,0,sizeof(closed));
  open.push(P(0,0));

  while(!open.empty()){
    P p = open.front(); open.pop();
    if(closed[p.second][p.first]) continue;
    closed[p.second][p.first] = true;

    res++;

    rep(i,4){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if(nx>=0 && w>nx && ny>=0 && h>ny && v[ny][nx]==color){
        open.push(P(nx,ny));
      }
    }
  }

  return res;
}

vvi draw(vvi v,int nextColor){
  int firstColor = v[0][0];
  queue<P> open;
  bool closed[h][w];

  memset(closed,0,sizeof(closed));
  open.push(P(0,0));

  while(!open.empty()){
    P p = open.front(); open.pop();
    if(closed[p.second][p.first]) continue;
    closed[p.second][p.first] = true;

    v[p.second][p.first] = nextColor;

    rep(i,4){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if(nx>=0 && w>nx && ny>=0 && h>ny && v[ny][nx]==firstColor){
        open.push(P(nx,ny));
      }
    }
  }

  return v;
}

int solve(vvi v,int rem){
  if(rem == 0){
    return area(v);
  }

  int res = 0;
  REP(i,1,7){
    if(rem == 1 && i != c) continue;
    res = max(res,solve(draw(v,i),rem-1));
  }
  return res;
}

int main(){
  while(cin>>h>>w>>c,h||w||c){
    vvi v(h);
    rep(i,h){
      v[i] = vi(w);
      rep(j,w) cin>>v[i][j];
    }
    cout<<solve(v,5)<<endl;
  }
}