AOJ : 1235 - Life Line

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1235
問題文中の図のように, 正三角形型のグラフが入力で与えられます. 各ノードには, 0~9 の値のいずれかが書かれています.
隣接している同じ値は全てひとまとめにして, これを一つのグループと呼びます. グループは, グループに隣接するノードに 0 がなければ, 全て 0 に変化します(問題文 Figure3b -> 3c).

この問題では, 入力 C (1 <= C <= 9) が与えられ, この数字をグラフの 0 のノードのどこかに書き込んだときの最高得点を求める問題です.
得点の計算法は次のとおりです.

• C を書き込んだとき, 0 に変化する C 以外のグループのノード数 = プラスの得点.
• C を書き込んだとき, 0 に変化する C のグループのノード数 = マイナスの得点.

例えば, Figure 4b -> 4c は, C = 2 のときで,

• C のグループ以外で消えたノード数 = +4
• C のグループで消えたノード数 = -3

となり, 4 - 3 = 1 が得点となります.

アルゴリズム

全探索で解けます.
0 のノードを順番に見ていって, C に変化させて, 得点がいくらか計算しながら最高得点を求めました.

プログラム

int n,c;
int t[10][10],used[10][10];
bool zeroFlg; //あるグループに 0 が隣接したかどうか

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

//グループのノード数を求める
int dfs(int x,int y,int number){
  int res = 1;
  used[y][x] = 1;

  rep(i,6){
    int nx = x + dx[i];
    int ny = y + dy[i];

    if(ny>=0 && ny<n && nx>=0 && nx<=ny){
      if(t[ny][nx]==0) zeroFlg = true;
      if(t[ny][nx]==number && !used[ny][nx]){
        int tmp = dfs(nx,ny,number);
        res += tmp;
      }
    }
  }
  return res;
}

//現在の配列 t の内容に対して最大点数を求める
int solve(void){
  memset(used,0,sizeof(used));
  int res = 0;
  rep(i,n) rep(j,i+1){
    if(t[i][j]>0 && !used[i][j]){
      zeroFlg = false;
      int tmp = dfs(j,i,t[i][j]);
      if(zeroFlg) continue;
      if(t[i][j] == c){
        res -= tmp;
      } else{
        res += tmp;
      }
    }
  }
  return res;
}

int main(void){
  while(cin>>n>>c,c||c){
    rep(i,n) rep(j,i+1) cin>>t[i][j];

    int ans = -1000;
    //0 のノードを順番に c に変えて探索する
    rep(i,n) rep(j,i+1) if(t[i][j]==0){
      t[i][j] = c;
      ans = max(ans,solve());
      t[i][j] = 0;
    }
    cout<<ans<<endl;
  }

  return 0;
}