AOJ 1174 Identically Colored Panels Connection

問題

問題文読んで。

解法

色の変化をdfsする。隣接するマスの判定もdfsで。

コード

int h,w,c;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int p[8][8];
bool ck[8][8];
bool valid(int x, int y){
  return x>=0&&x<w&&y>=0&&y<h;
}
void check(int x, int y, int c){
  if(ck[y][x]||p[y][x]!=c) return;
  ck[y][x] = true;
  REP(r,4){
    int nx = x+dx[r];
    int ny = y+dy[r];
    if(valid(nx,ny)){
      check(nx,ny,c);
    }
  }
}
int dfs(int t){
  int ret = 0;
  if(t==5){
    memset(ck,0,sizeof(ck));
    check(0,0,c);
    REP(y,h)REP(x,w)if(ck[y][x])ret++;
  }else{
    int tmp[8][8];
    memcpy(tmp,p,sizeof(p));
    REP(nc,6){
      memset(ck,0,sizeof(ck));
      check(0,0,p[0][0]);
      REP(y,h)REP(x,w)if(ck[y][x])p[y][x] = nc;
      ret = max(ret,dfs(t+1));
      memcpy(p,tmp,sizeof(tmp));
    }
  }
  return ret;
}
int main(){
  while(cin>>h>>w>>c,h){
    c--;
    REP(y,h)REP(x,w)cin>>p[y][x],p[y][x]--;
    cout<<dfs(0)<<endl;
  }
  return 0;
}