Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

回溯(剪枝)法

Posted by 18860012175 at 2020-05-14 11:32:48 on Problem 1753
/**
 * POJ1753,Accepted
 * 棋盘上每一个棋子都有翻转和不翻转两种选择
 * 总共16个棋子,就是2^16种可能
 * 问题的解是这所有可能的一个子集
 * 在此利用回溯法遍历子集树
 * 剪枝函数设定为:当前已经翻转的次数如果大于已经得到的最优次数则不再往下
 * 由于问题是求解最少的翻转次数,为了提高效率,回溯函数中优先搜索不翻转的情况
 * 这样的话搜索过程中翻转的次数就是递增的,一旦得到结果,剩余的翻转次数更多的情况会被剪枝
 * 每得到一个子集,检查棋盘状态和翻转次数是否更少(递归出口)
 */
#include <stdio.h>

int Checkerboard[16];//4x4棋盘,0代表白,1代表黑
int Count = 20;//记录最优翻转次数,由于最多翻转16次,初始化大于16的数
int times;//自动初始化0,记录当前已经翻转的次数,用于剪枝函数,若times>Count则没必要往下
bool Check(){//检查是否全部同色
    for(int i=0;i<16;++i){
        if(Checkerboard[0]!=Checkerboard[i])
            return false;
    }
    return true;
}
void Flip(int target){//翻转target及其上下左右棋子
    int r = target/4;//用于辨别边界棋子
    int c = target%4;//同上
    Checkerboard[target] = !Checkerboard[target];
    if(r>0) Checkerboard[target-4] = !Checkerboard[target-4];
    if(r<3) Checkerboard[target+4] = !Checkerboard[target+4];
    if(c>0) Checkerboard[target-1] = !Checkerboard[target-1];
    if(c<3) Checkerboard[target+1] = !Checkerboard[target+1];
}
void Backtrack(int i){
    if(i>=16){//得到一个子集
        if(Check()&&times<Count)    Count = times;
    }
    else{
        Backtrack(i+1);//优先不翻转,提高效率
        times++;//翻转后的总翻转次数
        int flag = 0;//标记是否翻转
        if(times<Count) {
            Flip(i);//翻转
            flag = 1;
            Backtrack(i+1);
        }
        if(flag) Flip(i);//回溯,恢复上一次状态
        times--;
    }
}
int main(){
    char ch;
    for(int i=0;i<16;++i){
        ch = getchar();
        if(ch=='\n'){
            --i;
            continue;
        }
        Checkerboard[i] = (119-ch)/21;//哈希函数,直接把w映射到0,b映射到1
    }
    Backtrack(0);
    if(Count==20)   printf("Impossible\n");
    else printf("%d\n",Count);
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator