`
lingyibin
  • 浏览: 196344 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

POJ1753-位操作

UP 
阅读更多

Flip Game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 11333 Accepted: 4818

Description

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules: 
  1. Choose any one of the 16 pieces. 
  2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).

Consider the following position as an example: 

bwbw 
wwww 
bbwb 
bwwb 
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become: 

bwbw 
bwww 
wwwb 
wwwb 
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal. 

Input

The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.

Output

Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).

Sample Input

bwwb
bbwb
bwwb
bwww

Sample Output

4

 

 

 

这是原题。

 

本题如果定义一个数组的话,遍历并判断状态 将是一件费时的事,此时可以想到用位来操作。

先讲一些位操作的基本知识:

int test = 0;

C中,int 有2个字节,C++/Java等语言中有4个字节,而一个字节有8位。

要使test的第一位变成1,则可做一个或运算:test | 1, 第二位变成1,则可这样:test | (1 << 1), 第三位变1,则:test | (1 << 2)。把某位变成0可以用与、非运算,如把第三位变成0,则test & ~(1 << 2) 。可以写一个程序试试:

 

#include<iostream>
using namespace std;

int main()
{
	int a = 1, b = 7; //7用2进制表示是111
	b &= ~(a <<2);
	cout<<b<<endl; //输出结果为3,用2进制表示是11
	return 0;
}

 要把两个数的各个位合并(就是有1即1),可用或运算,给一个示例:

 

	int a = 5, b = 3;
	a |= b;
	cout<<a<<endl; //答案7

 把两个数的各个位相减,用抑或或运算,示例:

 

	int a = 5, b = 3;
	a ^= b;
	cout<<a<<endl; //答案:6

 ……之后还遇到什么位运算再补充。。。

 

本题 可用16位来表示各个状态,两位一个,用1来表示black,0表示white。则65536是全black的情况,0是全白的情况,这样的话,要判断是否已经得出结果时,就不用遍历16个元素了!!!

如本题:

bwwb

bbwb

bwwb

bwww

状态值为6585,计算方法为

1*2^0+0*2^1+0*2^2..1*2^12+0*2^13..=6585

下面是网上摘取的一段代码,呵呵,写得比我的好,转此来学习。

 

在此基础上进行BFS搜索,首先理解一点,先点(0,0)再点(0,1)与先点(0,1)再点(0,0)对结果不造成任何影响.因此遍历棋盘的16个位置,将每次点击后的状态id利用树状结构保存.如:

                                  6585

                               /     |      \  ...

                           (0,0) (0,1)  (0,2)

                            /        |         \  ...

                         6568   6553   6646

                      ...............................

对此树进行BFS搜索,将id为0(全白)或65535(全黑)的时候则搜索成功,输出树的高度,否则输出"Impossible".

为了提高搜索效率,采用位运算,如果想将整数的二进制某一位翻转可采用id^=(1<<x)(x代表要翻转的位置)


 

#include "assert.h"
#include <iostream>
#include <queue>
using namespace std;

const int MAX_STATE = 65536;
const int ALL_WHILE_STATE = 0;
const int ALL_BLACK_STATE = 65535;
const int WIDTH_OF_BOARD = 4;
const int SIZE_OF_BOARD = WIDTH_OF_BOARD * WIDTH_OF_BOARD; // 4 * 4

int ConvertPieceColorToInt(char color)
{
    switch(color)
    {
    case 'b':
        return 1;
    case 'w':
        return 0;
    }
}

int FlipPiece(int state_id, int position)
{
    state_id ^= (1 << position);

    // up
    if(position - 4 >= 0)
        state_id ^= (1 << (position - 4));
    // down
    if(position + 4 < SIZE_OF_BOARD)
        state_id ^= (1 << (position + 4));
    // left
    if(position % 4 != 0)
        state_id ^= (1 << (position - 1));
    // right
    if(position % 4 != 3)
        state_id ^= (1 << (position + 1));

    return state_id;
}

int main()
{
    int current_state_id = 0;
    int state[MAX_STATE];
    queue<int> search_queue;

    memset(state, -1, sizeof(state));

    char color;

    for(int i = 0; i < SIZE_OF_BOARD; ++i)
    {
        cin >> color;
        current_state_id += ConvertPieceColorToInt(color) << i;
    }

    if(current_state_id == ALL_WHILE_STATE
        || current_state_id == ALL_BLACK_STATE)
    {
        cout << "0" << endl;
        return 0;
    }

    state[current_state_id] = 0;
    search_queue.push(current_state_id);

    int next_state_id;

    while(!search_queue.empty())
    {
        current_state_id = search_queue.front();
        search_queue.pop();

        for(int i = 0; i < SIZE_OF_BOARD; ++i)
        {
            next_state_id = FlipPiece(current_state_id, i);
            if(next_state_id == ALL_WHILE_STATE
                || next_state_id == ALL_BLACK_STATE)
            {
                cout << state[current_state_id] + 1 << endl;
                return 0;
            }
            assert(next_state_id < MAX_STATE);
            if(state[next_state_id] == -1 /* not visited */)
            {
                state[next_state_id] = state[current_state_id] + 1;
                search_queue.push(next_state_id);
            }
        }
    }

    cout << "Impossible" << endl;
    return 0;
}
分享到:
评论

相关推荐

    POJ1753-Flip Game

    翻转一行或一列对应的操作可以转化为位操作,如异或(XOR)等。 2. **广度优先搜索**:使用BFS遍历所有可能的操作序列。每个节点代表一次操作后的棋盘状态,边连接代表可行的操作。通过BFS可以找到达到目标状态的...

    POJ1942-Paths on a Grid

    动态规划方法可能用于计算每个格子到达终点的所有路径,而强制类型转换可能是在处理大整数乘法或路径计数时,为避免溢出而进行的操作。自定义精度输出则可能是因为结果可能涉及大量位的小数,需要特殊处理来保证输出...

    POJ2305-Basic remains

    6. **效率优化**:虽然这是一道基础题,但考虑到可能的大规模输入,优化算法以提高运行效率仍然是必要的,例如使用位操作或其他高效计算余数的方法。 7. **调试与测试**:在提交代码之前,开发者需要进行本地测试,...

    POJ1840-Eqs

    9. **位运算**:对于效率要求高的题目,位运算技巧可以提高代码运行速度。 10. **记忆化搜索**:当动态规划问题规模较大时,使用记忆化搜索可以避免重复计算,提高效率。 在实际的解题过程中,参赛者需要阅读题目...

    POJ1936-All in All

    具体到"ALL in ALL"这个题目名称,可能意味着需要处理全集或包含所有元素的情况,可能涉及到组合优化或集合操作。 2. **数据结构**:根据题目需求,可能会使用到数组、链表、树、图、堆栈、队列等数据结构,用于...

    POJ2602-Superlong sums

    总之,“POJ2602-Superlong sums”是一道关于大整数计算的编程题,挑战者需要设计并实现一种能够在超长整数范围内正确执行加法操作的方法。提供的代码示例使用了不同的数据结构和策略,可以作为学习和理解大整数运算...

    POJ2965-The Pilots Brothers' refrigerator

    在提供的代码文件中,"POJ2965-The Pilots Brothers' refrigerator(DFS+enum).cpp" 应该是使用DFS和枚举实现的解决方案,而 "POJ2965-The Pilots Brothers' refrigerator(DFS+Bit).cpp" 是使用DFS和位运算的版本。...

    POJ1027-The Same Game

    【标题】"POJ1027 - The Same Game"是一个经典的编程竞赛题目,源自北京大学的在线编程平台POJ(Problem Online Judge)。该题目主要考察的是动态规划和矩阵链乘法的知识,要求参赛者编写程序解决一个具有策略性的...

    POJ1503-Integer Inquiry

    POJ的编号系统通常是三位数字,便于管理和检索题目。 【文件列表】中的"POJ1503-Integer Inquiry.cpp"是一个C++源代码文件,很可能包含了实现该问题解决方案的代码。C++是一种通用的、面向对象的编程语言,因其高效...

    POJ1014-Dividing【DFS】【多重背包+二进制优化】

    但如果是有限次选取,我们可以用二进制变量来表示每个物品是否被选中,然后通过二进制搜索或位操作来优化解决方案的效率。 在给出的文件列表中,“POJ1014-Dividing【多重背包+二进制优化】.cpp”和“POJ1014-...

    POJ3094-Quicksum

    5. **位运算**:对于整数求和,可能会利用位运算的特性,如异或操作(XOR),在某些特定场景下可以快速求得数组元素的和。 6. **数学技巧**:在一些特定的数学问题中,可能存在特定的公式或者技巧可以快速得到答案...

    北大POJ初级-数学

    2. **逻辑与位运算**:在解决一些问题时,可能会用到位运算,如按位与、或、异或,以及左移、右移等操作。这些运算是计算机底层处理数据的基础,对于优化算法效率至关重要。 3. **排列组合**:在一些问题中,需要...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1753, poj2965 - **解释**:这一类问题通常涉及基本的数学运算和数学定理的应用。 #### 2. 几何问题 - **例题**:poj1328, poj2109, poj2586 - **解释**:这类题目涉及到几何图形的处理,比如点、线...

    POJ1000-1299中的80题AC代码

    5. **其他**:位操作、编码解码、模拟、图论问题(最短路径、最小生成树、网络流等)、递归、分治策略等。 每道题目都可能综合运用到多个知识点,而AC代码则代表了解决这些问题的有效方法。通过研究这些代码,我们...

    POJ3349-Snowflake Snow Snowflakes

    总的来说,POJ3349“Snowflake Snow Snowflakes”是一个涉及几何、位运算和组合优化的有趣问题,它要求程序员具备扎实的算法基础和良好的编程习惯,同时也锻炼了他们在面对复杂问题时的分析和解决问题的能力。...

    POJ1207-The 3n + 1 problem

    《POJ1207-The 3n + 1 problem》是北京大学在线编程平台POJ上的一道经典算法题目,其主要涉及的知识点是数论和动态规划。本题目的核心是解决著名的“Collatz Conjecture”问题,也被称为“3n+1猜想”。 3n+1猜想是...

    poj-1028-Web-Navigation.zip_poj

    6. 状态压缩:如果状态非常多,可能需要使用位操作进行状态压缩,以节省空间。 7. 性能优化:由于POJ对运行时间有严格限制,所以代码需要高效,避免不必要的计算和内存使用。 通过阅读和理解提供的代码,我们可以...

    ACM-POJ 算法训练指南

    1. **排序**:包括了基础的排序算法,如快速排序(poj1753, poj2965),是算法学习的基础。 2. **搜索**:涉及广度优先搜索(BFS)和深度优先搜索(DFS)(poj1328, poj2109, poj2586),是解决图问题的关键。 3. **...

    acm 分类 北大

    - 枚举:通过列举所有可能的情况来解决问题,如POJ1753和POJ2965。 - 贪心:选择当前最优解,逐步达到全局最优,如POJ1328和POJ2109。 - 递归和分治:将问题分解为更小的部分,如POJ2586。 - 递推:利用已知的较...

    算法-开关问题(POJ-1830)(包含源程序).rar

    4. **位操作**:如果开关的状态可以用二进制表示,那么位操作(如位移、与、或、异或)可能有助于高效地处理状态变化。 5. **回溯法**:如果存在多个解决方案,回溯法可以帮助找到所有可能的答案,而不仅仅是第一个...

Global site tag (gtag.js) - Google Analytics