首页 > 代码库 > poj1753解题报告（枚举、组合数）

poj1753解题报告（枚举、组合数）

2024-07-06 20:23:46   225人阅读

 

POJ 1753，题目链接http://poj.org/problem?id=1753

题意：

有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几个格子可以使4*4的正方形变为纯白或者纯黑？

 

思路：

1. 每一个位置只有两种颜色，翻偶数次等于没有翻，所以只有翻基数次对棋盘有影响，即只用考虑一个位置最多翻一次。

2. 一共有16个位置，所以最多翻16次。那么可能翻0次就成功、或者翻1次成功、或者翻2次成功...或者翻16次成功。

3. 每个位置翻转的顺序对结果无影响。

那么这就变成了一个组合数问题：

将输入的16个元素放到一个数组中，进行组合数计算即可。（组合数+枚举）

 

代码1：

?
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
88
89
90
91
92
93
94
95
96
97
/*
* Memory: 384K
* Time: 16MS
*/
#include <cstdio>
#include <cstdlib>
#define ALLNUM 16
 
static int count = 0;
/*
* 15 14 13 12
* 11 10  9  8
*  7  6  5  4
*  3  2  1  0
*/
void flip(int& data, int posIdx)
{
    data ^= 1<<posIdx;
    //up
    if (posIdx < 12) data ^= 1<<(posIdx+4);
    //down
    if (posIdx > 3)  data ^= 1<<(posIdx-4);
    //left
    if (posIdx%4+1 != 4) data ^= 1<<(posIdx+1);
    //right
    if (posIdx%4 != 0) data ^= 1<<(posIdx-1);
}
 
bool isOK(int data)
{
    if (data =http://www.mamicode.com/= 0 || data == 0xffff) return true;
    else return false;
}
 
/*
* num 1 -- ALLNUM
* starIdx 0 -- ALLNUM-1
*/
void func(int num, int starIdx, int data, int step)
{
//  printf("-----------comein >> starIdx=%d, num=%d\n", starIdx, num);
    if (num == 1){
        ++step;
        for (int i=starIdx; i<ALLNUM; ++i){
            int temp = data;
            flip(temp, i);
            if (isOK(temp)) {
                printf("%d\n", step);
                exit(0);
            }
 
            //log
            ++count;
        }
    }
    else if (starIdx+num <= ALLNUM){ // 14 + 2 <= 16  (14 15)
        ++step;
        for (int i=starIdx; i<=ALLNUM-num; ++i){
            int temp = data;
            flip(temp, i);
            func(num-1, i+1, temp, step);
        }
    }
//  else {
//      printf("Error Branch----------- >> starIdx=%d, num=%d\n", starIdx, num);
//  }
}
 
// black 0, white 1
int main()
{
    int num = ALLNUM;
    int data = http://www.mamicode.com/0;
    char c;
    while (true)
    {
        scanf("%c", &c);
        if (c == ‘\n‘) continue;
        --num;
        if (c == ‘w‘) data ^= 1<<num;
        if (num == 0)  break;
    }
     
    if (isOK(data)) {
        printf("0\n");
        return 0;
    }
 
    for (int i=1; i<=ALLNUM; ++i)
    {
        func(i, 0, data, 0);
//      printf("i=%d,AllCount=%d\n", i, count);
    }
 
    printf("Impossible\n");
    return 0;
}

 

代码2：

?
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
//356K 313MS
#include <cstdio>
#include <cstdlib>
#define ALLNUM 16
bool isOK(int data)
{
    if (data =http://www.mamicode.com/= 0 || data == 0xffff) return true;
    else return false;
}
void flip(int& data, int posIdx)
{
    data ^= 1<<posIdx;
    //up
    if (posIdx < 12) data ^= 1<<(posIdx+4);
    //down
    if (posIdx > 3)  data ^= 1<<(posIdx-4);
    //left
    if (posIdx%4+1 != 4) data ^= 1<<(posIdx+1);
    //right
    if (posIdx%4 != 0) data ^= 1<<(posIdx-1);
}
// black 0, white 1
int main()
{
    int num = ALLNUM;
    int data = http://www.mamicode.com/0;
    char c;
    while (true)
    {
        scanf("%c", &c);
        if (c == ‘\n‘) continue;
        --num;
        if (c == ‘w‘) data ^= 1<<num;
        if (num == 0)  break;
    }
    int step = ALLNUM;
    bool bImpossible = true;
    for (int i=0; i<=0xffff; ++i)
    {
        int tempData = http://www.mamicode.com/data;
        int tempStep = 0;
        for (int idx=0; idx<ALLNUM; ++idx){
            if ((1<<idx) & i){ //idx位置需要翻转
                flip(tempData, idx);
                ++tempStep;
            }
        }
        if (isOK(tempData) && tempStep < step) step = tempStep;
    }
    if (step == ALLNUM)
        printf("Impossible\n");
    else
        printf("%d\n", step);
    return 0;
}

 

 

 

 

 

 


联系
我们