POJ 1753 flip game (DFS 𞓜 bit operation)

poj 1753 Flip Game

Niu Ke topic
poj subject

The main idea of the topic ： That means there is one 4*4 The chessboard of , There are... On the chessboard 16 Black and white pieces are placed randomly b It stands for black chess pieces ,w Represents white chess pieces , Now we can operate the chessboard to change the color of the pieces so that the whole chessboard will eventually have only one color of the pieces , The operation is to flip the pieces , A white chess piece turns black , vice versa , Flip one piece at a time , There are four around it （ On 、 Next 、 Left 、 Right ） All four pieces must be turned over , Find the minimum number of flips , A piece that has only one color on the final chessboard .

Output ： If the current status is consistent with the title, then do not flip , Direct output 0, If the recursion still fails to change to the state conforming to the topic, the output will be Impossible, Otherwise, the minimum number of flips is output

Method 1 ：dfs+ enumeration

Here are two functions in the code

Function one ：change function

Because what the title requires is to flip the pieces selected by itself and add the pieces up, down, left and right , We can find that the coordinates of these five cases contain at least one 0, They are （0, 0）, （1, 0）,（ 0, 1）, （-1, 0）,（ 0, -1）, They multiply to 0, Other multiplied by 1 perhaps -1

We can also change it change function , Change it to our common dfs Traversal , In fact, they are much the same

void change(int x, int y)
{
    
    for (int i = -1; i <= 1; ++i)
        for (int j = -1; j <= 1; ++j)
        {
    
            if (i * j == 1 || i * j == -1) // Exclude other directions , Keep it up, down, left and right 
                continue;
            if (x + i >= 1 && x + i <= 4 && y + j >= 1 && y + j <= 4) // Judge whether it is within the scope 
            {
                                                             // Add yourself to the top, bottom, left and right, and turn them over 
                if (c[x + i][y + j] == 'w')
                    c[x + i][y + j] = 'b';
                else
                    c[x + i][y + j] = 'w';
            }
        }
}

After modification -----> common dfs Traverse the way

int d[5][2] = {
    0, 0, 1, 0, 0, 1, -1, 0, 0, -1};
void change(int x, int y)
{
    
    for (int i = 0; i < 5; ++i)
    {
    
        int dx = x + d[i][0];
        int dy = y + d[i][1];
        if (dx >= 1 && dx <= 4 && dy >= 1 && dy <= 4)
        {
    
            if (c[dx][dy] == 'w')
                c[dx][dy] = 'b';
            else
                c[dx][dy] = 'w';
        }
    }
}

Function two ：dfs function
Analyze the pruning function inside , I feel that if I write it, I may not think of cutting it like this , Very clever pruning indeed , Traversal is two levels for loop , Every time the outer layer circulates , The inner loop goes through all the situations , So the first case is i<n When , We don't need to enumerate him anymore , Because even now j>m, We have already enumerated , The second case , When i==n When , If at this time j<m There is no need to enumerate . Because it has already been enumerated , Every time we enumerate a point , There is no need to enumerate the points before the current point , At that time, I wanted to change the pruning operation to if(i<=n&&j<=m) So we'll find out , We have many branches that are unnecessary to enumerate without subtracting （ Because it has been enumerated, for example （n-1,m+1））, It's obviously going to be overtime

We use it num Record the number of flips , Once the final state is reached , So directly update

void dfs(int n, int m, int num)
{
    
    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
        {
                                        // The enumerated cases do not need to be enumerated 
            if (i < n || (i == n && j <= m)) // Pruning operation 
                continue;
            change(i, j);             // Change the status of the current point and the upper, lower, left and right points 
            if (judge() && num < ans) // What we require is the minimum number of flips , If the final state is reached and the number of flips is less than the previous one, update it 
            {
    
                all = 1;
                ans = num;
            }
            dfs(i, j, num + 1); // Continue recursion not found 
            change(i, j);       // Recursion to the last time to change back 
        }
}

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
char c[100][100];
int ans = 1000;
void change(int x, int y)
{
    
    for (int i = -1; i <= 1; ++i)
        for (int j = -1; j <= 1; ++j)
        {
    
            if (i * j == 1 || i * j == -1) // Exclude other directions , Keep it up, down, left and right 
                continue;
            if (x + i >= 1 && x + i <= 4 && y + j >= 1 && y + j <= 4) // Judge whether it is within the scope 
            {
                                                             // Add yourself to the top, bottom, left and right, and turn them over 
                if (c[x + i][y + j] == 'w')
                    c[x + i][y + j] = 'b';
                else
                    c[x + i][y + j] = 'w';
            }
        }
}

int judge() // Judge whether it has met the meaning of the topic 
{
    
    char a = c[1][1];
    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
            if (c[i][j] != a)
                return 0;
    return 1;
}

int all = 0;
void dfs(int n, int m, int num)
{
    
    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
        {
                                        // The enumerated cases do not need to be enumerated 
            if (i < n || (i == n && j <= m)) // Pruning operation 
                continue;
            change(i, j);             // Change the status of the current point and the upper, lower, left and right points 
            if (judge() && num < ans) // What we require is the minimum number of flips , If the final state is reached and the number of flips is less than the previous one, update it 
            {
    
                all = 1;
                ans = num;
            }
            dfs(i, j, num + 1); // Continue recursion not found 
            change(i, j);       // Recursion to the last time to change back 
        }
}

int main()
{
    
    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
            scanf(" %c", &c[i][j]);
    if (judge()) // If you have already met the status of the topic at the beginning, it will be output 0
    {
    
        all = 1;
        ans = 0;
    }
    else
        dfs(0, 0, 1); // Otherwise recursion 
    if (all)
        printf("%d\n", ans);
    else
        puts("Impossible");
}

Method 2 ： An operation

To tell you the truth, bit operation looks like a headache

Bit operation reference link

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
using namespace std;
const int N = 55;
int a[N], b[N];
int x[N], c[N];
int num[N];
int ans = 0x3f3f3f3f;

int get_num(int tmp)
{
    
    int cnt = 0;
    while (tmp)
    {
    
        if (tmp & 1)
            ++cnt;
        tmp >>= 1;
    }
    return cnt;
}

void deal(int a[])
{
    
    memset(c, 0, sizeof(c));
    for (x[1] = 0; x[1] < 1 << 4; ++x[1])
    {
    
        int cnt = num[x[1]];
        c[1] = a[1] ^ x[1] ^ (x[1] >> 1) ^ ((x[1] << 1) & 15);
        c[2] = a[2] ^ x[1];
        for (int i = 2; i <= 4; ++i)
        {
    
            x[i] = c[i - 1];
            cnt += num[x[i]];
            c[i] = c[i] ^ x[i] ^ (x[i] >> 1) ^ ((x[i] << 1) & 15);
            c[i + 1] = a[i + 1] ^ x[i];
        }
        if (!c[4])
            ans = min(ans, cnt);
    }
}

int main()
{
    
    for (int i = 0; i < 1 << 4; ++i)
        num[i] = get_num(i);
    for (int i = 1; i <= 4; ++i)
        for (int j = 0; j < 4; ++j)
        {
    
            char s;
            scanf(" %c", &s); // ' %c' Eliminate carriage returns 
            if (s == 'b')
                a[i] |= 1 << j;
            else
                b[i] |= 1 << j;
        }
    deal(a);
    deal(b);
    if (ans == 0x3f3f3f3f)
        puts("Impossible");
    else
        printf("%d\n", ans);
    return 0;
}

I recently finished reading what Chai Jing wrote 《 See 》, I like to say that “ Tell the truth , People who do the real thing ”

Don't go too far , Forget why we started . If you are sad , We will not set out again , What's the point of your leaving ———— Tabanus chenense

Don't go too far , Forget why we started . If you are sad , We will not set out again , What's the point of your leaving ———— Tabanus chenense