`
zhenzxie
  • 浏览: 68197 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

第一次用位运算和十六进制数_poj1753

    博客分类:
  • Code
 
阅读更多
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.rar_poj 1753_poj1753" 提供的资源是关于POJ1753编程挑战的解决方案,其中包括了完整的代码实现以及实验报告。POJ(Problem Online Judge)是中国大学常用的在线编程竞赛平台,它提供了一系列的...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    ACM.zip_ACM_poj_poj3187_poj3669

    ACM_poj_poj3187_poj3669" 提供的信息表明,这个压缩包包含的是与ACM(国际大学生程序设计竞赛)相关的编程题目解决方案,具体是POJ(Programming Online Judge)平台上的两道题目,编号分别为poj3187和poj3669。...

    pku1151.rar_Atlantis_pku 11_poj Atlant_poj Atlantis_poj11

    标题中的“pku1151.rar_Atlantis_pku 11_poj Atlant_poj Atlantis_poj11”似乎是指北京大学(Peking University, PKU)编程竞赛中的一道题目,编号为1151,与“Atlantis”这个主题相关。这道题目在多个平台上也被提及...

    POJ.rar_poj java_poj1048

    约瑟夫环问题的解决方案通常使用链表或者循环数组来模拟圈子,用一个计数器来记录报数。在Java中,可以创建一个`LinkedList`或者自定义数组类来存储人,然后遍历链表或数组,每次报数到特定值时删除相应的人。对于...

    poj2775.rar_poj_poj 27_poj27_poj2775

    综合以上信息,我们可以推测这个压缩包是为了帮助用户理解和解决POJ平台上的第2775号编程挑战,重点在于理解并实现一个涉及递归的算法。学习这个题目不仅可以提高编程技巧,还能深入理解递归思想及其在实际问题中的...

    poj1038--Bugs.rar_Bugs_poj 1038 _poj10_poj1038

    POJ(Problemset Online Judge)是一个在线编程竞赛平台,它提供了一系列的问题供参赛者解决,旨在锻炼和提升编程能力,特别是算法设计与实现的能力。编号为1038的题目被称为“Bugs”,这可能是一个关于程序错误或...

    poj_2682(3).rar_C++ 数组扩充_poj 26_poj 2682_poj26

    标题中的"poj_2682(3).rar"是一个指向编程竞赛问题的引用,通常这类问题在网站如POJ(Programming Online Judge)上出现,供程序员解决并提交代码进行测试。这个问题的编号是2682,可能涉及到特定的数据结构或算法...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    POJ1753-Flip Game

    每个棋盘的状态可以用一个整数表示,其中每一位代表一个方格的颜色。翻转一行或一列对应的操作可以转化为位操作,如异或(XOR)等。 2. **广度优先搜索**:使用BFS遍历所有可能的操作序列。每个节点代表一次操作后的...

    poj_1699.rar_1699_poj_poj1699

    【标题】"poj_1699.rar_1699_poj_poj1699" 提供的是一个关于POJ(编程在线判题系统)第1699题的解决方案,其中包含了该问题的代码实现和解题思路。POJ是一个流行的在线编程竞赛平台,它为参赛者提供了各种算法题目,...

    1010_stamps.zip_1010_POJ 1010_poj_poj stamps_poj10

    总的来说,POJ 1010邮票问题是一个典型的动态规划实例,它锻炼了程序员对问题建模、状态转移方程构造和优化算法的能力。通过深入理解和实践这个题目,可以提升编程技能,更好地应对类似的问题挑战。

    string-problem(POJ).rar_POJ 19_poj

    标题中的"string-problem(POJ).rar_POJ 19_poj"表明这是一个与ACM编程竞赛相关的压缩包,特别关注的是字符串处理问题。在ACM编程竞赛中,字符串问题是一个常见的类别,通常涉及到字符串的查找、比较、操作、模式匹配...

    poj1990.rar_POJ 19_poj_poj19

    总结起来,POJ 1990题目是一个考察数据结构和算法应用能力的典型问题,通过合理利用两个树状数组,我们可以有效地解决区间查询和更新的需求。理解并熟练掌握树状数组的原理和操作方法,对于提升编程竞赛的解题技巧至...

    pku_poj_2187.rar_poj 2187_凸包问题

    标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...

    poj2488.rar_poj24_poj2488_方向模板法

    标题中的“poj2488.rar_poj24_poj2488_方向模板法”指的是一个解决编程竞赛问题POJ2488的压缩文件,其中可能包含了解决该问题的代码示例。POJ是Programming Online Judge的缩写,是一个在线的编程竞赛平台,参与者...

    poj3601.rar_POJ3601_poj 36_visual c

    【标题】"POJ3601.rar" 是一个压缩包文件,主要包含了对北京大学在线评测系统(Online Judge)上的一道题目——POJ 3601的解答和相关实验报告。"POJ 3601"是这道编程问题的编号,通常在编程竞赛或练习平台中,每个...

    POJ3277.rar_3277 poj_poj3277_多个面积_线段树

    标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...

    poj.rar_poj

    标题中的"poj.rar_poj"暗示了这是一个与POJ(Programming Online Judge)相关的压缩文件,POJ是一个在线编程竞赛平台,主要供程序员们练习和提交算法解决方案。在这个压缩包中,很可能包含了用户在POJ上参与编程挑战...

    Poj_1102_.rar_poj11

    标题"Poj_1102_.rar_poj11"暗示了这是一个关于解决Poj_1102问题的资源包,通常在编程竞赛或在线判题系统如POJ(Problem Set of Judge Online)上遇到。POJ是中国的一个在线编程训练平台,提供了各种算法题目供用户...

Global site tag (gtag.js) - Google Analytics