UVA – 10651 – Pebble Solitaire

Straight forward Bit-Mask problem you just have to think reverse (how many pebble can i remove?)

import java.util.Arrays;
import java.util.Scanner;
public class Pr10651 {
	static int[] masks = new int[1 << 12];
	//http://goo.gl/6TtTgf
	static int setbit(int mask, int idx, int val) {
		return (val == 1) ? (mask | (1 << idx)) : (mask & ~(1 << idx));
	}

	static boolean getBit(int mask, int idx) {
		return ((mask >> idx) & 1) == 1;
	}

	static int cntBit(int mask) {
		int cnt = 0;
		while (mask > 0) {
			if (mask % 2 == 1)
				cnt++;
			mask /= 2;
		}
		return cnt;
	}

	private static int best(int mask) {
		// TODO Auto-generated method stub
		if (masks[mask] != -1)
			return masks[mask];
		masks[mask] = 0;
		for (int i = 0; i < 10; i++) {
			if (getBit(mask, i) && getBit(mask, i + 1) && !getBit(mask, i + 2)) {
				int tmask = mask;
				tmask = setbit(tmask, i, 0);
				tmask = setbit(tmask, i + 1, 0);
				tmask = setbit(tmask, i + 2, 1);
				masks[mask] = Math.max(masks[mask], 1 + best(tmask));
			}
			if (!getBit(mask, i) && getBit(mask, i + 1) && getBit(mask, i + 2)) {
				int tmask = mask;
				tmask = setbit(tmask, i, 1);
				tmask = setbit(tmask, i + 1, 0);
				tmask = setbit(tmask, i + 2, 0);
				masks[mask] = Math.max(masks[mask], 1 + best(tmask));
			}
		}
		return masks[mask];
	}

	public static void main(String[] args) {
		Arrays.fill(masks, -1);
		Scanner in = new Scanner(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int mask = 0;
			String u = in.next();
			for (int i = 0; i < 12; i++) {
				if (u.charAt(i) == 'o')
					mask = setbit(mask, i, 1);
			}
			System.out.println(cntBit(mask) - best(mask));
		}
	}
}