1235-Life Line

問題概要

空のマスと隣接していない同じ数字のグループを消去することを考える．
その数字が自分の数字だった場合，数字の個数だけスコアが引かれ，それ以外なら数字の個数だけスコアが増えるものとする．
空のマスに一つに自分の数値を当てはめた時の得点の最大を求めよ．

解法

ハミカム構造とみなしてBFS．
実装問題．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
#include <set>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
int n,c;
int MAP[100][100];
int dx[6]={-1,1,0,1,0,-1},dy[6]={0,0,1,1,-1,-1};
bool valid(int x,int y){
	if(x>=0&&x<n&&y>=0&&y<=x)return true;
	return false;
}
//消すべきマスか判定する
bool bfs(int x,int y){
	if(MAP[x][y]==0)return false;
	int c=MAP[x][y];
	typedef pair<int,int> P;
	queue<P> que;
	set<P> ac;
	que.push(P(x,y));
	while(!que.empty()){
		P now=que.front();que.pop();
		if(ac.find(now)!=ac.end())continue;
		ac.insert(now);
		REP(i,6){
			int nx=now.first+dx[i],ny=now.second+dy[i];
			if(valid(nx,ny)&&MAP[nx][ny]==c){
				que.push(P(nx,ny));
			}
			if(valid(nx,ny)&&MAP[nx][ny]==0){
				return false;
			}
		}
	}
	return true;
}
//スコア計算
int solve(){
	int del[15][15];
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			del[i][j]=bfs(i,j);
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			if(del[i][j]){
				if(MAP[i][j]==c){
					ans--;
				}else{
					ans++;
				}
			}
		}
	}
	return ans;
}
int main(){
	while(cin>>n>>c){
		if((n|c)==0)break;
		for(int i=0;i<n;i++){
			for(int j=0;j<=i;j++){
				cin>>MAP[i][j];
			}
		}
		int ans=-99999999;
		for(int i=0;i<n;i++){
			for(int j=0;j<=i;j++){
				if(MAP[i][j]==0){
					MAP[i][j]=c;
					ans=max(ans,solve());
					MAP[i][j]=0;
				}
			}
		}
		cout<<ans<<endl;

	}
}