http://poj.org/problem?id=1753
(1)题意:一个4*4的棋盘,上面放着棋子,棋子要么白色朝上,要么黑色朝上。每一次翻动棋子有两个规则:①只能是16个中的一个。②翻动一个棋子,那么它的上下左右也都要翻动(存在的话)。要求输出使棋盘全为黑或全为白的最少翻动次数。
(2)思想:①搜索方法是用BFS。②翻动棋子采用的是异或运算,所以程序定义了一个int数组。为了表示方便int数组中的数采用十六进制数表示。
(3)Java实现:
package id0000_1999;
import java.util.ArrayDeque;
import java.util.Scanner;
/**
* 3768K 2985MS ac
*/
public class Id1753 {
//最后两个是棋盘上棋子全黑或着全白的表示。
static int[] op = new int[] { 0x0000c800, 0x0000e400, 0x00007200,
0x00003100, 0x00008c80, 0x00004e40, 0x00002720, 0x00001310,
0x000008c8, 0x000004e4, 0x00000272, 0x00000131, 0x0000008c,
0x0000004e, 0x00000027, 0x00000013, 0x0000ffff, 0x00000000 };
public static void main(String[] args) {
char[] arr;
int chess = 0, count = 0;
Scanner sc = new Scanner(System.in);
while (count < 4) {
arr = sc.nextLine().toCharArray();
for (int i = 0; i < 4; i++) {
chess <<= 1;
if (arr[i] == 'b')
chess++;
}
count++;
}
if (chess == op[16] || chess == op[17]) {
System.out.println(0);
return;
}
arr = null;
sc = null;// 没用的变量名设为null,不知道这样能不能省内存.
count = 0;
Node n;
ArrayDeque<Node> queue = new ArrayDeque<Node>();
while (count < 16) {
int temp = chess ^ op[count];
if (temp == op[16] || temp == op[17]) {
System.out.println(1);
return;
}
n = new Node(count, 1, temp);
//第十六个棋子翻动后诺不能满足要求则不用加到队列中,节约内存。
if (count != 15) {
queue.add(n);
}
count++;
}
while (queue.size() != 0) {
n = queue.pollFirst();
int state = n.state;
int num = n.num + 1;
int step = n.step + 1;
while (num < 16) {
int temp = state ^ op[num];
if (temp == op[16] || temp == op[17]) {
System.out.println(step);
return;
} else {
if (num != 15) {
queue.add(new Node(num, step, temp));
}
}
num++;
}
}
System.out.println("Impossible");
}
}
class Node {
int num;
int step;
int state;
public Node(int num, int step, int state) {
this.num = num;
this.step = step;
this.state = state;
}
}
分享到:
相关推荐
【标题】"POJ1753.rar_poj 1753_poj1753" 提供的资源是关于POJ1753编程挑战的解决方案,其中包括了完整的代码实现以及实验报告。POJ(Problem Online Judge)是中国大学常用的在线编程竞赛平台,它提供了一系列的...
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...
ACM_poj_poj3187_poj3669" 提供的信息表明,这个压缩包包含的是与ACM(国际大学生程序设计竞赛)相关的编程题目解决方案,具体是POJ(Programming Online Judge)平台上的两道题目,编号分别为poj3187和poj3669。...
标题中的“pku1151.rar_Atlantis_pku 11_poj Atlant_poj Atlantis_poj11”似乎是指北京大学(Peking University, PKU)编程竞赛中的一道题目,编号为1151,与“Atlantis”这个主题相关。这道题目在多个平台上也被提及...
约瑟夫环问题的解决方案通常使用链表或者循环数组来模拟圈子,用一个计数器来记录报数。在Java中,可以创建一个`LinkedList`或者自定义数组类来存储人,然后遍历链表或数组,每次报数到特定值时删除相应的人。对于...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
综合以上信息,我们可以推测这个压缩包是为了帮助用户理解和解决POJ平台上的第2775号编程挑战,重点在于理解并实现一个涉及递归的算法。学习这个题目不仅可以提高编程技巧,还能深入理解递归思想及其在实际问题中的...
POJ(Problemset Online Judge)是一个在线编程竞赛平台,它提供了一系列的问题供参赛者解决,旨在锻炼和提升编程能力,特别是算法设计与实现的能力。编号为1038的题目被称为“Bugs”,这可能是一个关于程序错误或...
标题中的"poj_2682(3).rar"是一个指向编程竞赛问题的引用,通常这类问题在网站如POJ(Programming Online Judge)上出现,供程序员解决并提交代码进行测试。这个问题的编号是2682,可能涉及到特定的数据结构或算法...
每个棋盘的状态可以用一个整数表示,其中每一位代表一个方格的颜色。翻转一行或一列对应的操作可以转化为位操作,如异或(XOR)等。 2. **广度优先搜索**:使用BFS遍历所有可能的操作序列。每个节点代表一次操作后的...
【标题】"poj_1699.rar_1699_poj_poj1699" 提供的是一个关于POJ(编程在线判题系统)第1699题的解决方案,其中包含了该问题的代码实现和解题思路。POJ是一个流行的在线编程竞赛平台,它为参赛者提供了各种算法题目,...
总的来说,POJ 1010邮票问题是一个典型的动态规划实例,它锻炼了程序员对问题建模、状态转移方程构造和优化算法的能力。通过深入理解和实践这个题目,可以提升编程技能,更好地应对类似的问题挑战。
标题中的"string-problem(POJ).rar_POJ 19_poj"表明这是一个与ACM编程竞赛相关的压缩包,特别关注的是字符串处理问题。在ACM编程竞赛中,字符串问题是一个常见的类别,通常涉及到字符串的查找、比较、操作、模式匹配...
总结起来,POJ 1990题目是一个考察数据结构和算法应用能力的典型问题,通过合理利用两个树状数组,我们可以有效地解决区间查询和更新的需求。理解并熟练掌握树状数组的原理和操作方法,对于提升编程竞赛的解题技巧至...
标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...
标题中的“poj2488.rar_poj24_poj2488_方向模板法”指的是一个解决编程竞赛问题POJ2488的压缩文件,其中可能包含了解决该问题的代码示例。POJ是Programming Online Judge的缩写,是一个在线的编程竞赛平台,参与者...
【标题】"POJ3601.rar" 是一个压缩包文件,主要包含了对北京大学在线评测系统(Online Judge)上的一道题目——POJ 3601的解答和相关实验报告。"POJ 3601"是这道编程问题的编号,通常在编程竞赛或练习平台中,每个...
标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...
标题中的"poj.rar_poj"暗示了这是一个与POJ(Programming Online Judge)相关的压缩文件,POJ是一个在线编程竞赛平台,主要供程序员们练习和提交算法解决方案。在这个压缩包中,很可能包含了用户在POJ上参与编程挑战...
标题"Poj_1102_.rar_poj11"暗示了这是一个关于解决Poj_1102问题的资源包,通常在编程竞赛或在线判题系统如POJ(Problem Set of Judge Online)上遇到。POJ是中国的一个在线编程训练平台,提供了各种算法题目供用户...