Poj 1753-Flip Game(DFS)

发布于 2019-07-23  708 次阅读


题意:

给你16枚硬币,4 × 4排列。
每一次操作使一枚硬币连同它的上下左右四枚硬币翻转
问最少几次操作,使得所有的硬币同一面
如果不能完成,则输出Impossible

分析:

16个硬币,每个这有两种状态,翻转或者不翻转
也就是说最多只翻转 16 个,最少翻转 0 个。
因此,最多只有 2 ^ 16 种情况,这个数不大,只有六万多吧
所以这一题可以用深搜,直接把所有的情况搜索一遍
这个深搜的过程纠结了好久,一开始想歪了
每一个位置两种情况,先判断不翻转的情况,然后再判断翻转的情况

最后不要忘了再翻过来!!!!
#include <iostream>
#include <cmath>

using namespace std;

const int MAXN = 4;

int G[MAXN][MAXN];
int vis[MAXN][MAXN];

bool judge()
{
    int ans = 0;
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            ans += G[i][j];
    if (ans == 0 || ans == 16)
        return true;
    else
        return false;
}

void flip(int x, int y)
{
    G[x][y] ^= 1;
    if (x-1 >= 0) G[x-1][y] ^= 1;
    if (x+1 < MAXN) G[x+1][y] ^= 1;
    if (y-1 >= 0) G[x][y-1] ^= 1;
    if (y+1 < MAXN) G[x][y+1] ^= 1;
}
int ans = 0x3f3f3f3f, f = 0;
void DFS(int x, int y, int t)
{
    if (judge())
    {
        f = 1;
        ans = min(ans, t);
        return;
    }
    if (x >= MAXN || y >= MAXN)
        return ;

    int nx = (x+1) % MAXN;
    int ny = y + (x+1)/MAXN; 
    // 当前位置不反转,进入下一个位置
    DFS(nx, ny, t);
    // 当前位置反转,进入下一个位置
    flip(x, y); 
    DFS(nx, ny, t+1);
    //把当前位置再次反过来
    flip(x, y);

    return ;
}

int main()
{
    char c;
    for (int i = 0; i < MAXN; i++)
    {
        for (int j = 0; j < MAXN; j++)
        {
            cin >> c;
            if (c == 'b') G[i][j] = 1;
            else          G[i][j] = 0;
        }
    }
    DFS(0, 0, 0);
    if (f)
        cout << ans << endl;
    else
        cout << "Impossible" << endl;
    
    return 0;
}


Simple And Clear