POJ 1753 Flip Game(BFS+状态压缩)
http://poj.org/problem?id=1753
题意:有一个4*4的黑白棋盘,棋盘上的子是两面的,一面黑,一面白.你每次选取一个子把它和它上下左右相邻的4个子都翻转,使得他们从黑变白或从白变黑.问你最少需要操作多少下可以使得所有子颜色统一.
分析:
棋盘一共16个位置,所以我们用一个16位二进制数来表示棋盘的状态.同样适用BFS,要用到vis[1<<16]和dist[1<<16]的数组.
当要翻转(i,j)格子的时候,那么对应16位二进制数中的i*4+j位二进制位.(想想是不是).
且(i,j)周围的4个对应格子也会相应的翻转,不过要注意(i,j)周围的4个格子不一定有位置.可能(i,j)是边界.
写代码的时候,有2个BUG,至少花了我40分钟才找到,就是两个不小心,结果花了这么久.
AC代码:
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int vis[65540],dist[65540];
int dr[]={-1,1,0,0};//上,下,左,右
int dc[]={0,0,-1,1};
int BFS(int st)
{
if(st==0 || st+1==(1<<16)) return 0;
queue<int> Q;
//memset(vis,0,sizeof(vis));
vis[st]=1;
dist[st]=0;
Q.push(st);
while(!Q.empty())
{
int s=Q.front();Q.pop();
for(int i=0;i<16;i++)
{
int ns=s;//ns是新生成的状态,s是原始状态 错误1,这句话我原先写到了上面的for循环外面,无限wa 之前还在脑子里 闪了下会不会是这里错了,果然
int r=i/4,c=i%4;
ns^=1<<i;
for(int d=0;d<4;d++)
{
int nr=r+dr[d];
int nc=c+dc[d];
if(nr>=0&&nr<4&&nc>=0&&nc<4)
ns^=1<<(nr*4+nc);
}
if(ns==0 || ns+1==(1<<16)) return dist[s]+1;
if(vis[ns]==0)
{
Q.push(ns);
vis[ns]=1; //错误2 这里我写成了vis[ns]==1 ,以前也犯过一次这个错
dist[ns]=dist[s]+1;
}
}
}
return -1;
}
int main()
{
char maze[10][10];
for(int i=0;i<4;i++)
scanf("%s",maze[i]);
int st=0;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(maze[i][j]=='b')
st=st|(1<<(i*4+j));
int ans=BFS(st);
if(ans==-1) printf("Impossible");
else printf("%d",ans);
return 0;
}
分享到:
相关推荐
北大POJ1753-Flip Game 解题报告+AC代码
POJ1753 Flip Game题目完整代码及报告
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
该题记录了本人研究该题的记录,有些是心得,希望能给大家帮助。
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ1184-Smart typist【搜索与状态压缩】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj1085,记忆化DP+状态压缩求解
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ2002-Squares 解题报告+AC代码