AOJ1235 Life Line

問題リンク Life Line

• 概要

石とりゲームをする。プレイヤーの番号をCとする。ほかのプレイヤーの番号はC以外の1〜9の数字である。
大きさNの正三角形上の空マスに自分の石を置いたとき、得られる得点の最大値を求めよ。
得点とは（自分の番号以外の取り除いた石の合計 - 自分の番号の取り除いた石の合計）である。
石を取り除く状態は次のようなときに起こる。
まず、同じ番号の石同士が隣接していたらそれらはグループ化される。グループ化された石の集合の全てについて空白マスが1つも隣接していない場合、そのグループは取り除かれる。
3<=N<=10
1<=C<=9

• 解法

全ての空きマスに対して石を置いてみて、得点の最大値を探すのが基本方針です。
まず、自分の番号以外の石についてグループ化させておきます。グループに属している石の個数と、そのグループに隣接している空きマスの座標を覚えておきます。これをLとします。
次に空きマス i を探して自分の石を置きます。このとき、自分の番号の石についてグループ化します。これをmineとします。
このとき、Lの中で、隣接する空きマス数が1でその空きマスが i であるようなものがあれば、そのグループは取り除かれ、グループに属する石の個数分だけ得点します。同様にmineの中で、隣接する空きマスがないものがあれば、そのグループは取り除かれ、グループに属する石の個数分だけ減点します。
正三角形上の座標の取り扱い方について説明します。まず、1次元配列で座標を管理します。上から順に0から番号付けします。上から d 段目にある座標 i について隣接している6マスは
左上： i-d ただし、iが最上段でない かつ 左端でない
右上： i-d+1　ただし、iが最上段でない かつ 右端でない
左　： i-1　　ただし、左端でない
右　： i+1　　ただし、右端でない
左下： i+d　　ただし、最下段でない
右下： i+d+1　ただし、最下段でない
によってアクセスできます。

グループ化を行う処理ですが、幅優先探索によって実装しました。深さ優先にした場合、最悪の潜る深さが5000程度になるのでスタックオーバーフローが起きるかもしれないと思ったからです。

• ソース

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

//Life Line
public class AOJ1235 {

	class R{
		Set<Integer> s, empty;
		public R() {
			s = new HashSet<Integer>();
			empty = new HashSet<Integer>();
		}
	}
	
	int N, C, n, max;
	int[] map, depth;
	boolean[] top, bottom, left, right;
	boolean[] u;

	R bfs(int focus, int i){
		R res = new R();
		List<Integer> list = new ArrayList<Integer>();
		list.add(i);
		u[i] = true;
		while(!list.isEmpty()){
			List<Integer> next = new ArrayList<Integer>();
			for(int j:list){
				if(map[j]==0){
					res.empty.add(j); continue;
				}
				res.s.add(j);
				int d = depth[j];
				if(!top[j]&&!left[j]&&!u[j-d]&&(map[j-d]==0||map[j-d]==focus)){
					if(map[j-d]==focus)u[j-d] = true;
					next.add(j-d);
				}
				if(!top[j]&&!right[j]&&!u[j-d+1]&&(map[j-d+1]==0||map[j-d+1]==focus)){
					if(map[j-d+1]==focus)u[j-d+1] = true;
					next.add(j-d+1);
				}
				if(!left[j]&&!u[j-1]&&(map[j-1]==0||map[j-1]==focus)){
					if(map[j-1]==focus)u[j-1] = true;
					next.add(j-1);
				}
				if(!right[j]&&!u[j+1]&&(map[j+1]==0||map[j+1]==focus)){
					if(map[j+1]==focus)u[j+1] = true;
					next.add(j+1);
				}
				if(!bottom[j]&&!u[j+d]&&(map[j+d]==0||map[j+d]==focus)){
					if(map[j+d]==focus)u[j+d] = true;
					next.add(j+d);
				}
				if(!bottom[j]&&!u[j+d+1]&&(map[j+d+1]==0||map[j+d+1]==focus)){
					if(map[j+d+1]==focus)u[j+d+1] = true;
					next.add(j+d+1);
				}
			}
			list = next;
		}
		return res;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			N = sc.nextInt(); C = sc.nextInt();
			if((N|C)==0)break;
			n = N*(N+1)/2;
			map = new int[n]; depth = new int[n];
			top = new boolean[n]; bottom = new boolean[n]; left = new boolean[n]; right = new boolean[n];
			int d = 1, k = 0;
			for(int i=0;i<n;i++){
				map[i] = sc.nextInt();
				depth[i] = d;
				top[i] = d==1; bottom[i] = d==N;
				left[i] = k==0; right[i] = k==d-1;
				k++;
				if(k==d){
					k = 0; d++;
				}
			}
			u = new boolean[n];
			List<R> l = new ArrayList<R>();
			for(int i=0;i<n;i++){
				if(u[i]||map[i]==C||map[i]==0)continue;
				l.add(bfs(map[i], i));
			}
			int max = -n;
			for(int i=0;i<n;i++){
				if(map[i]!=0)continue;
				map[i] = C;
				List<R> mine = new ArrayList<R>();
				u = new boolean[n];
				for(int j=0;j<n;j++){
					if(u[j]||map[j]!=C)continue;
					mine.add(bfs(C, j));
				}
				int p = 0;
				for(R r:l)if(r.empty.size()==1&&r.empty.contains(i))p+=r.s.size();
				for(R r:mine)if(r.empty.isEmpty())p-=r.s.size();
				max = Math.max(max, p);
				map[i] = 0;
			}
			System.out.println(max);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1235().run();
	}
}