翻纸牌游戏
Time Limit : 9000/3000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 5 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
有一种纸牌游戏，很有意思，给你N张纸牌，一字排开，纸牌有正反两面，开始的纸牌可能是一种乱的状态（有些朝正，有些朝反），现在你需要整理这些纸牌。但 是麻烦的是，每当你翻一张纸牌（由正翻到反，或者有反翻到正）时，他左右两张纸牌（最左边和最右边的纸牌，只会影响附近一张）也必须跟着翻动，现在给你一 个乱的状态，问你能否把他们整理好，使得每张纸牌都正面朝上，如果可以，最少需要多少次操作。
Input
有多个case，每个case输入一行01符号串（长度不超过20），1表示反面朝上，0表示正面朝上。
Output
对于每组case，如果可以翻，输出最少需要翻动的次数，否则输出NO。
Sample Input
01 011
Sample Output
NO 1
Author
思路：BFS + 回溯，最终结果一定会小于0101001的长度（位数），这是因为如果大于它的长度，那么一定
会有某些0或者1，被主动翻了二次或者以上，这是不可能出现的，因为这是重复的，所以最终结果一定会小
于0101001的长度（位数），每一位翻或者不翻，然后次数最小，需要通过回溯求解，注意对于每一张牌来说
只有两种操作
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define INF 0xffffff;
int map[22];
char str[22];
int hash[22];
int len;
int ans;
int temp;
bool shut_dowm()
{
for(int i = 1;i <= len;i ++)
if(map[i])
return false;
return true;
}//判断是否已经全部处理好了
void DFS(int x)
{
if(shut_dowm())//如果全部处理好了
{
temp = 0;
for(int i = 1;i <= len;i ++)
if(hash[i] == 1)
temp ++;
if(temp < ans)
ans = temp;
return ;//寻找另外可能的解
}
if(x >= len + 1)
return ;
for(hash[x] = 0;hash[x] < 2;)
{
map[x] ^= 1;
hash[x] ++;
if(x > 1)
map[x - 1] ^= 1;
if(x < len)
map[x + 1] ^= 1;
DFS(x + 1);
}
}
int main()
{
while(~scanf("%s",str))
{
len = strlen(str);
memset(map,0,sizeof(map));
for(int i = 0;i < len;i ++)
map[i + 1] = str[i] - 48;
memset(hash,0,sizeof(hash));
ans = INF;
DFS(1);
if(ans != 0xffffff)
printf("%d ",ans);
else
printf("NO ");
memset(str,0,sizeof(str));
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define INF 0xffffff;
int map[22];
char str[22];
int hash[22];
int len;
int ans;
int temp;
bool shut_dowm()
{
for(int i = 1;i <= len;i ++)
if(map[i])
return false;
return true;
}//判断是否已经全部处理好了
void DFS(int x)
{
if(shut_dowm())//如果全部处理好了
{
temp = 0;
for(int i = 1;i <= len;i ++)
if(hash[i] == 1)
temp ++;
if(temp < ans)
ans = temp;
return ;//寻找另外可能的解
}
if(x >= len + 1)
return ;
for(hash[x] = 0;hash[x] < 2;)
{
map[x] ^= 1;
hash[x] ++;
if(x > 1)
map[x - 1] ^= 1;
if(x < len)
map[x + 1] ^= 1;
DFS(x + 1);
}
}
int main()
{
while(~scanf("%s",str))
{
len = strlen(str);
memset(map,0,sizeof(map));
for(int i = 0;i < len;i ++)
map[i + 1] = str[i] - 48;
memset(hash,0,sizeof(hash));
ans = INF;
DFS(1);
if(ans != 0xffffff)
printf("%d ",ans);
else
printf("NO ");
memset(str,0,sizeof(str));
}
return 0;
}