Wx::

POJ 1753

记录这道题是因为以回溯(dfs)的思想解题过程中,我先使用「子集树」,超时!而改为「判定树」,通过!

  • 子集树:对于每个节点,对于其所有可取的值进行遍历,并在遍历中每一次改变状态后继续下一次遍历(递归),完成递归后修复回原状态,并进行下一个状态的取值

  • 判定树:对于每个节点,其所有可取的值仅有 0 和 1(两种状态),即「存在 - 不存在」,或「改变 - 不改变」


poj 1753 题目:

原文:http://poj.org/problem?id=1753

对于一个 4 × 4 的棋盘,每格放一个棋子,棋子有两种状态:一面白(w),一面黑(b)。
每次翻转一个棋子,且与该棋子相邻的上、下、左、右四个棋子自动翻转。
求可使全部棋子均为黑或均为白的最少翻转次数。

注意: 翻转顺序不影响结果,对同一棋子的多次翻转相当于 0 或 1 次翻转


子集树解法:

详情:-brev-

  • 首先判定初始状态是否为成功(ok)状态,若不是,则继续

  • 对于 16 颗棋子,先选择任意 1 颗翻转,(即限制最多翻转 1 次),有 16 种情况,
    for(int i = 0; i < 16; i++)
    若将 16 颗棋子都试过后仍未出现成功状态,继续

  • 任意翻转 2 颗,(即限制最多翻转 2 次)

    for(int i = 0; i < 15; i++)
        for(int j = 0; j < 16; j++)
    

    检测是否能出现成功状态,若未出现,继续

  • 以此类推...

代码:
// 以一维数组存储棋盘初始状态:
bool a[16]; // 'b' == true; 'w' == false
int flip = 0; // 递归中当前的翻转棋子数
int flipLimit = 0; // 翻转上限
bool found = false; // 是否成功

bool ok() { // 判定成功状态,即所有棋子颜色一样
    for (int i = 0; i < 16; i++) {
        if (a[i] != a[0]) {
            return false;
        }
    }
    return true;
}

// 一次翻转(上下左右同时翻转)
void reverse(int i) {
    int t = i % 4;
    a[i] = !a[i];
    if (i > 3)
        a[i - 4] = !a[i - 4];
    if (i < 12)
        a[i + 4] = !a[i + 4];
    if (t > 0)
        a[i - 1] = !a[i - 1];
    if (t < 3)
        a[i + 1] = !a[i + 1];
}

// 回溯
void back(int t) {
    // 初始 t 都为 0
    if (flip >= flipLimit) {
        // 若翻转次数达到了预定限制次数
        if (ok()) {
            cout << flipLimit << endl;
            found = true;
        }
        return;
    }

    // 限制翻转 flipLimit 次时,第 i 个可翻转棋子的下标范围:
    int n = 16 - flipLimit + t + 1;

    // 第 i 次翻转的下标可取 t 到 n:
    for (int i = t; i < n; i++) {
        if (!found && flip<flipLimit) {
            flip++;
            reverse(i);
            back(t + 1);
            flip--;
            reverse(i);
        }
        else {
            return;
        }
    }
}

int main() {
    char c;
    for (int i = 0; i < 16; i++) {
            cin >> c;
            a[i] = (c == 'b') ? true : false;
    }

    // 翻转限制由 0 次一直到 16 次,若产生成功状态即停止,获得了最少的翻转次数:
    for (flipLimit = 0; flipLimit <= 16; flipLimit++) {
        flip = 0;
        back(0);
        if (found) {
            break;
        }
    }

    // 16 次都试过了还没成功,即不可能成功(因为一共 16 颗棋子
    if (!found) {
        cout << "Impossible" << endl;
    }

    return 0;
}

over


判定树解法:

  • 对每个棋子,均有两种状态,翻 or 不翻,遍历 16 颗棋子的这两种状态,共 216 种,即可知道是否存在成功(ok)状态。因此回溯(back)即可。

  • 复杂度:一层递归(相比子集树的循环套递归套循环耗时少了许多)

代码:
#include <iostream>
using namespace std;

// 用一维数组存棋盘初始状态:
bool a[16]; // 'b' == true; 'w' == false
int flip = 0; // 回溯中当前翻转次数
int flipM = 17; // 最小翻转次数
bool found = false; // 是否找到成功状态

// 判定是否颜色一样:
bool ok() {
    for (int i = 0; i < 16; i++) {
        if (a[i] != a[0]) {
            return false;
        }
    }
    return true;
}

// 一次翻转(上下左右同时翻转)
void reverse(int i) {
    int t = i % 4;
    a[i] = !a[i];
    if (i > 3)
        a[i - 4] = !a[i - 4];
    if (i < 12)
        a[i + 4] = !a[i + 4];
    if (t > 0)
        a[i - 1] = !a[i - 1];
    if (t < 3)
        a[i + 1] = !a[i + 1];
}

void back(int t) {
    // 先判定当前是否成功:
    if (ok()) {
        if (flip < flipM) {
            flipM = flip;
        }
        return;
    }

    // 当前下标为 16 即返回(数组下标 0..15):
    if (t > 15) {
        return;
    }

    back(t + 1); // 不翻转直接进行下一次

    if (flip < flipM-1) {
        // 回溯剪枝,若当前翻转次数小于当前最小翻转次数减一时:
        reverse(t);
        flip++;
        back(t + 1);
        reverse(t);
        flip--;
    }

}

int main() {
    char t;
    for (int i = 0; i < 16; i++) {
        cin >> t;

        // 为方便翻转取反,以 bool 类型存颜色:
        a[i] = t == 'b' ? true : false;
    }

    back(0);

    if (flipM > 16) {
        cout << "Impossible" << endl;
    }
    else {
        cout << flipM << endl;
    }

    return 0;
}


more

更多 Poj 题解:


7

评论(0

评论 取消
验证码:
搜索