POJ 1753 Flip Game

Posted on | In | 阅读

太久不练实在是手生啊，干脆从POJ的分类题目开始重新训练。虽然研究僧时间还是蛮紧的，但是还是要抽点时间出来啊！！！😂

七灯问题变形，一共有16个开关，递归枚举变动的个数

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

bool isSame(int* pan){
    for(int i = 1; i < 16; i++){
        if(pan[i] != pan[i-1])
            return false;
    }
    return true;
}

void flip(int* pan, int pos){
    int x = pos / 4;
    int y = pos % 4;
    pan[pos] = !(pan[pos]);
    if(y < 3){
        pan[pos+1] = !(pan[pos+1]);
    }
    if(y > 0){
        pan[pos-1] = !(pan[pos-1]);
    }
    if(x < 3){
        pan[pos + 4] = !(pan[pos + 4]);
    }
    if(x > 0){
        pan[pos - 4] = !(pan[pos - 4]);
    }
}

bool dfs(int* pan, int cur, int len, int curPos){
    if(cur == len)
        if(isSame(pan)){
            return true;
        }
    else
        return false;
    if(16 - curPos < len - cur)
        return false;
    int* new_pan = new int[16];
    for(int i = curPos; i < 16; i++){
        for(int j = 0; j < 16; j++){
            new_pan[j] = pan[j];
        }
        flip(new_pan, i);
        if(dfs(new_pan, cur+1, len, i+1)){
            return true;
        }
    }
    return false;
}

int main()
{
    int pan[16];
    char row[5];
    int pos = 0;
    for(int i = 0; i < 4; i++){
        scanf("%s", row);
        getchar();
        for(int j = 0; j < 4; j++){
            if(row[j] == 'b')
                pan[pos++] = 0;
            else
                pan[pos++] = 1;
        }
    }
    if(isSame(pan)){
        printf("0\n");
    }else{
        int ans;
        int i;
        for(i = 1; i <= 16; i++){
            /*number of flipped*/
            if(dfs(pan, 0, i, 0)){
                printf("%d\n", i);
                break;
            }
        }
        if(i == 17)
            printf("Impossible\n");
    }
    return 0;
}