http://poj.org/problem?id=1753
import java.io.BufferedInputStream;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
static boolean[] isVisited = new boolean[65536];
public static void main(String[] args) {
Scanner scan = new Scanner(new BufferedInputStream(System.in));
if (scan.hasNext()) {
int[][] chessBoard = new int[4][4];
for (int i = 0; i < 4; i++) {
String ss = scan.nextLine().trim();
char[] cs = ss.toCharArray();
for (int j = 0; j < 4; j++) {
if (cs[j] == 'b') {
chessBoard[i][j] = 1;//black 1
} else if (cs[j] == 'w') {
chessBoard[i][j] = 0;//white 0
}
}
}
int result = bfs(chessBoard);
if (result == -1) {
System.out.println("Impossible");
} else {
System.out.println(result);
}
}
}
static int bfs(int[][] chessBoard) {
LinkedList<Node> queue = new LinkedList();
int id = chessBoardToId(chessBoard);
Node node = new Node(id,0);
if (isWhite(id) || isBlack(id)) {
return 0;
}
isVisited[id] = true;
queue.addLast(node);
while (!queue.isEmpty()) {
node = queue.removeFirst();
for (int i = 0; i < 16; i++) {
//16 childNode
Node nextNode = nextNode(node, i);
nextNode.addDepth();
int idid = nextNode.getChessBoardId();
if (!isVisited[idid]) {
isVisited[idid] = true;
queue.addLast(nextNode);
}
if (isWhite(idid) || isBlack(idid)) {
int d = nextNode.getDepth();
return d;
}
}
}
return -1;
}
static int chessBoardToId(int[][] chessBoard) {
int id = 0;
for (int i = 0; i < chessBoard.length; i++) {
for (int j = 0; j < chessBoard[i].length; j++) {
if (chessBoard[i][j] == 1) {
id++;
}
id <<= 1;
}
}
id >>= 1;
return id;
}
static Node nextNode(Node node, int i) {
int id = node.getChessBoardId();
int depth = node.getDepth();
id ^= (1 << (15 - i));
if (i >= 4) {
id ^= (1 << (15 - i + 4));
}
if (i <= 11) {
id ^= (1 << (15 - i - 4));
}
if (i % 4 > 0) {
id ^= (1 << (15 - i + 1));
}
if ((i + 1) % 4 > 0) {
id ^= (1 << (15 - i - 1));
}
node = new Node(id,depth);
return node;
}
static boolean isWhite(int chessBoardId) {
if (chessBoardId == 0) {
return true;
}
return false;
}
static boolean isBlack(int chessBoardId) {
if (chessBoardId == 0xFFFF) {
return true;
}
return false;
}
}
class Node {
private int chessBoardId;
private int depth;
public Node(int chessBoardId,int depth) {
this.chessBoardId = chessBoardId;
this.depth = depth;
}
public int getChessBoardId() {
return chessBoardId;
}
public void setChessBoardId(int chessBoardId) {
this.chessBoardId = chessBoardId;
}
public int getDepth() {
return depth;
}
public void addDepth() {
this.depth++;
}
}