AOJ 1235 - Life Line

問題概要

N段のピラミッド構造が入力として与えられ、これは下図のようなノードとエッジの関係がある。

各ノードには0〜9の数字が書かれている。このとき、入力として与えられた値Cを任意の値が0のノードに上書きしたとき、次のルールに従い、得られる得点の最大値を求めよ。

ルール

全てのノードに対して隣接する全ての同じ数字をグループ化する。そしてそのグループが値0のノードに接してなければそのグループの数のポイントを得られる。ただしそのグループがCならばその数だけポイントを失う。

制約

3 ≤ N ≤ 10
1 ≤ C ≤ 9

解法

全探索。
値が0の全てのノードに対してCに上書きし、得られる結果の最大を取る。

コード

#include <bits/stdc++.h>
  
using namespace std;
  
int N,C,cnt;
bool flg,visited[10][10];
vector<int> G[10];
int dx[6] = {-1,-1,0,0,1,1};
int dy[6] = {-1,0,-1,1,0,1};
  
bool inField(int x,int y){
  if(x > y || y >= N || x < 0 || y < 0){
    return false;
  }
  return true;
}
  
bool dfs(int x,int y,int c){
  if(G[y][x] == 0) return true;
  if(G[y][x] != c || visited[y][x]) return false;
  visited[y][x] = true; cnt++;
  bool res = false;
  for(int i = 0 ; i < 6 ; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(!inField(nx,ny)) continue;
    res |= dfs(nx,ny,c);
  }
  return res;
}
 
int solve(int x,int y){
  int res = 0;
  memset(visited,false,sizeof(visited));
  for(int i = 0 ; i < N ; i++){
    for(int j = 0 ; j <= i ; j++){
      if(G[i][j] == 0) continue;
      if(visited[i][j]) continue;
       
      cnt = 0; flg = false;
      if(dfs(j,i,G[i][j])) continue;
      res += (G[i][j] != C ? cnt : -cnt);
    }
  }
  return res;
}
  
int main(){
  int in;
  while(cin >> N >> C,(N|C)){
    for(int i = 0 ; i < N ; i++){
      G[i].clear();
      for(int j = 0 ; j <= i ; j++){
        cin >> in;
        G[i].push_back(in);
      }
    }
    int res = INT_MIN;
    for(int i = 0 ; i < N ; i++){
      for(int j = 0 ; j <= i ; j++){
        if(G[i][j] == 0){
          G[i][j] = C;
          res = max(res,solve(j,i));
          G[i][j] = 0;
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}