Description

Input

Output

Sample Input

bwwb

bbwb

bwwb

bwww

Sample Output

4

Source

import java.util.ArrayDeque;

import java.util.Scanner;

/*

 * 首先有两点：

 * 1.两颗棋子的翻动顺序不影响翻动结果

 * 2.一颗棋子的偶数次翻动与0次翻动效果等同，一颗棋子的奇数次翻动与1次翻动效果等同

 *

 */

public class poj1753 {

	public static void main(String[] args) {

		Scanner cin=new Scanner(System.in);

		while (cin.hasNext()){

			ArrayDeque<Node> qu=new ArrayDeque<Node>();//Java队列

			Node node=new Node(0,0,0);

			for (int i=1;i<=4;i++){

				String s=cin.next();

				for (int j=0;j<s.length();j++){

					char c=s.charAt(j);

					if (c=='b') {

						node.state=(node.state<<1)+1;//黑棋子则将当前状态表示的二进制位设为1

					}else{

						node.state=node.state<<1;//白棋子则将当前状态表示的二进制位设为0

					}

				}

			}

			qu.add(node);//初始状态增加队列

			boolean flag=false;

			while (qu.size()!=0){

				Node tou=qu.pop();//队头出队。以此队头衍生出下一颗棋子的翻动，并增加队尾

				if (tou.state==0 || tou.state==(1<<16)-1){//(1<<16)-1的二进制位为16个1

					System.out.println(tou.ways);//找到方法输出翻动棋子数

					flag=true;

					break;

				}

				if (qu.size()>0xFFFF) continue;//所有可能状态所有入队。不在有新的状态入队，下面循环体不再运行

				for (int i=tou.location+1;i<=16;i++){//从当前头节点的位置向后找，1到16表示16个棋格的翻动

					//状态（后改动），当前为第i个棋格的翻动。翻动棋格数为队头棋格翻动数+1

					node=new Node(0,i,tou.ways+1);

					//翻动当前棋子：队头与当前棋格翻动状态（比如左上角i=1状态为1后15个 0，即1000000000000000）的“异或”

					node.state=tou.state^(1<<(16-i));

					//翻动上相邻棋子：i-4>=1推断当前棋格是否有上相邻棋子

					if (i-4>=1) node.state^=1<<(16-i+4);

					//翻动下相邻棋子:i+4<=16推断当前棋格是否有下相邻棋子

					if (i+4<=16) node.state^=1<<(16-i-4);

					//翻动右相邻棋子:4的倍数为棋盘的右边界，无右相邻棋子，16-i再减1位运算少向左移动一位，所以是右边

					if (i%4!=0) node.state^=1<<(16-i-1);

					//翻动左相邻棋子:i-1为有边界时，加1后的i就是左边界

					if ((i-1)%4!=0) node.state^=1<<(16-i+1);

					qu.add(node);

				}

			}

			if (!flag)//找不出合适翻动

				System.out.println("Impossible");

		}

	}

}

class Node{

	int state;//状态：state的二进制位表示16个棋格的状态

	int location;//位置：当前状态为第i个棋格的翻动

	int ways;//翻动棋格数

	Node (int state,int location,int ways){

		this.state=state;

		this.location=location;

		this.ways=ways;

	}

}

java的ArrayDeque的使用

题目大意：4X4的一个棋盘上有白子（"w"）和黑子（"b"），棋子的还有一面是相反的颜色，翻动一颗棋子。上下左右跟着翻动。问至少要翻动几颗棋子，才干使棋盘全白或全黑