本文主要是介绍POJ 1753 Flip Game(bfs枚举+递推），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：http://poj.org/problem?id=1753
这题此前曾经做过，但当时是用的纯BFS做的，然后后来又做了一次组队赛，那是16*16的，果断超时超内存。。能超的都超了。。于是又找了个更好的方法，就是枚举第一行，然后后面的根据第一行的情况推下去。比如，你要让所有的都变成W，如果上一行的对应位置是B的话，那它就必须要翻转。这样能保证前三行的都是W，然后只需判断最后一行就可以判断是不是全翻成了W。代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>using namespace std;
int mp[20], min1, ff=0;
struct node
{int a[20], x, ans;
};
void bfs()
{int i, j;min1=1000000;queue<node>q;node f1, f2;for(i=0; i<16; i++){f1.a[i]=mp[i];}f1.x=0;f1.ans=0;q.push(f1);while(!q.empty()){f1=q.front();q.pop();if(f1.x==4){int ans1=0, ans2=0, flag=0;for(i=0; i<16; i++){f2.a[i]=f1.a[i];}f2.ans=f1.ans;for(i=4; i<16; i++){if(f2.a[i-4]==0){f2.a[i-4]=1-f2.a[i-4];f2.a[i]=1-f2.a[i];if(i%4>0)f2.a[i-1]=1-f2.a[i-1];if(i%4<3)f2.a[i+1]=1-f2.a[i+1];if(i+4<16)f2.a[i+4]=1-f2.a[i+4];ans1++;}}for(i=12; i<16; i++){if(f2.a[i]==0){flag=1;break;}}if(flag==0){if(min1>f2.ans+ans1)min1=f2.ans+ans1;ff=1;}for(i=0; i<16; i++){f2.a[i]=f1.a[i];}f2.ans=f1.ans;flag = 0;for(i=4; i<16; i++){if(f2.a[i-4]==1){f2.a[i-4]=1-f2.a[i-4];f2.a[i]=1-f2.a[i];if(i%4>0)f2.a[i-1]=1-f2.a[i-1];if(i%4<3)f2.a[i+1]=1-f2.a[i+1];if(i+4<16)f2.a[i+4]=1-f2.a[i+4];ans2++;}}for(i=12; i<16; i++){if(f2.a[i]==1){flag=1;break;}}if(flag==0){if(min1>f2.ans+ans2)min1=f2.ans+ans2;ff=1;}continue ;}for(i=0; i<16; i++){f2.a[i]=f1.a[i];}f2.x=f1.x+1;f2.ans=f1.ans;q.push(f2);f2.a[f1.x]=1-f1.a[f1.x];if(f1.x>=1){f2.a[f1.x-1]=1-f1.a[f1.x-1];}if(f1.x<3){f2.a[f1.x+1]=1-f1.a[f1.x+1];}f2.a[f1.x+4]=1-f1.a[f1.x+4];f2.ans=f1.ans+1;q.push(f2);}
}
int main()
{char s[10];int i, j;for(i=0; i<4; i++){scanf("%s",s);for(j=0; j<4; j++){if(s[j]=='w')mp[4*i+j]=1;elsemp[4*i+j]=0;}}bfs();if(ff)printf("%d\n",min1);elseprintf("Impossible\n");return 0;
}
这篇关于POJ 1753 Flip Game(bfs枚举+递推）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
