POJ 1753 Flip Game（回溯）
POJ 1753 Flip Game（回溯）
Michael阿明
发布于 2021-02-20 10:49:52
发布于 2021-02-20 10:49:52
1. 题目
1.1 题目链接
http://poj.org/problem?id=1753
1.2 题目大意
一个黑白棋子的棋盘，一个反过来周围四个也跟着反过来(如果存在的话)，颜色取反，问最少反转次数使得颜色全白或者全黑，不存在解的话输出信息。
1.3 解题思路
采用回溯算法，暴力枚举
2. 代码
2.1 Wrong Answer代码
/**
* @description:
* @author: michael ming
* @date: 2019/7/11 22:09
* @modified by:
*/
#include <iostream>
#include <string>
using namespace std;
bool a[4][4];
bool isok()//判断是否都是同种颜色
{
int i, j;
for(i = 0; i < 4; ++i)
{
for(j = 0; j < 4; ++j)
{
if(a[i][j] != a[0][0])
{
return false;
}
}
}
return true;
}
void flipAndUpdate(int r, int c)//翻转r，c处及其周围棋子
{
a[r][c] = !a[r][c];
if(r-1 >= 0)
a[r-1][c] = !a[r-1][c];
if(r+1 < 4)
a[r+1][c] = !a[r+1][c];
if(c-1 >= 0)
a[r][c-1] = !a[r][c-1];
if(c+1 < 4)
a[r][c+1] = !a[r][c+1];
}
void flip(int r, int c,int curstep, long &minstep)
{
if(isok())
{
if(curstep < minstep)
minstep = curstep;
return;
}
if(c+1 < 4)
flip(r,c+1,curstep,minstep);
else if(c+1 == 4 && r+1 < 4)
flip(r+1,0,curstep,minstep);
flipAndUpdate(r,c);
curstep++;
if(c+1 < 4)
flip(r,c+1,curstep,minstep);
else if(c+1 == 4 && r+1 < 4)
flip(r+1,0,curstep,minstep);
flipAndUpdate(r,c);//翻完了，还要复原？
}
int main()
{
string s;
int i, j;
long minstep = 65536;
for(i = 0; i < 4; ++i)
{
cin >> s;
for(j = 0; j < 4; ++j)
{
if(s[j] == 'b')
a[i][j] = 1;
else
a[i][j] = 0;
}
}
flip(0,0,0,minstep);
if(minstep == 65536)
cout << "Impossible" << endl;
else
cout << minstep;
return 0;
}2.2 Accepted代码
上面代码范围有问题，改动如下
AC 代码如下
/**
* @description:
* @author: michael ming
* @date: 2019/7/11 22:09
* @modified by:
*/
#include <iostream>
#include <string>
using namespace std;
bool a[5][5];
bool isok()//判断是否都是同种颜色
{
int i, j;
for(i = 0; i < 4; ++i)
{
for(j = 0; j < 4; ++j)
{
if(a[i][j] != a[0][0])
{
return false;
}
}
}
return true;
}
void flipAndUpdate(int r, int c)//翻转r，c处及其周围棋子
{
a[r][c] = !a[r][c];
if(r-1 >= 0)
a[r-1][c] = !a[r-1][c];
if(r+1 < 4)
a[r+1][c] = !a[r+1][c];
if(c-1 >= 0)
a[r][c-1] = !a[r][c-1];
if(c+1 < 4)
a[r][c+1] = !a[r][c+1];
}
void flip(int r, int c,int curstep, long &minstep)
{
if(isok())
{
if(curstep < minstep)
minstep = curstep;
return;
}
if(r == 4)
return;
if(c+1 < 4)
flip(r,c+1,curstep,minstep);
else if(c+1 == 4)
flip(r+1,0,curstep,minstep);
flipAndUpdate(r,c);
curstep++;
if(c+1 < 4)
flip(r,c+1,curstep,minstep);
else if(c+1 == 4)
flip(r+1,0,curstep,minstep);
flipAndUpdate(r,c);//翻完了，还要复原？
}
int main()
{
string s;
int i, j;
long minstep = 65536;
for(i = 0; i < 4; ++i)
{
cin >> s;
for(j = 0; j < 4; ++j)
{
if(s[j] == 'b')
a[i][j] = 1;
else
a[i][j] = 0;
}
}
flip(0,0,0,minstep);
if(minstep == 65536)
cout << "Impossible" << endl;
else
cout << minstep;
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/07/12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号