AOJ 1174 Identically Colored Panels Connection

問題

Identically Colored Panels Connection

解法

全探索で解けます。O(6⁵)ぐらい

心臓に悪いコード

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

void count(int y, int x){
  f[y][x] = 1;
  rep(d, 4){
    int ny = y+dy[d], nx = x+dx[d];
    if(ny < 0 || nx < 0 || ny >= h || nx >= w || p[ny][nx] != c || f[ny][nx]) continue;
    count(ny, nx);
  }
}

void change(int y, int x, int to, int from){
  f[y][x] = 1;
  p[y][x] = to;
  rep(d, 4){
    int ny = y+dy[d], nx = x+dx[d];
    if(ny < 0 || nx < 0 || ny >= h || nx >= w || p[ny][nx] != from || f[ny][nx]) continue;
    change(ny, nx, to, from);
  }
}

int dfs(int n){
  int res = 0;
  if(n == 4){
    memset(f, 0, sizeof(f));
    change(0, 0, c, p[0][0]);
    memset(f, 0, sizeof(f));
    count(0, 0);
    rep(y, h) rep(x, w) if(f[y][x]) res++;
    return res;
  }
  int tmp[8][8];
  rep(i, 6){
    rep(y, h) rep(x, w) tmp[y][x] = p[y][x];

    memset(f, 0, sizeof(f));
    change(0, 0, i, p[0][0]);
    res = max(res, dfs(n+1));
  return res;
}

int main(){
  while(scanf("%d%d%d", &h, &w, &c) && h+w+c){
    c--;
    rep(i, h) rep(j, w){
      scanf("%d", &p[i][j]);
      p[i][j]--;
    }
    printf("%d\n", dfs(0));
  }
  return 0;
}