P6183 [USACO10MAR] The Rock Game S

程序猿杀进CSDN原力榜，排名31！！！

 

P6183 [USACO10MAR] The Rock Game S

# [USACO10MAR] The Rock Game S

## 题目描述

在奶牛回家休息和娱乐之前，Farmer John 希望它们通过玩游戏获得一些智力上的刺激。游戏板由 $n$ 个相同的孔组成，这些孔最初**都是空的**。一头母牛要么用石头盖住一个洞，要么揭开一个先前被盖住的洞。**游戏状态**的定义是哪些洞被石头覆盖，哪些洞没有覆盖。游戏的目标是让奶牛准确地到达每个可能的游戏状态一次，然后返回到所有洞都没有覆盖的状态。以下是他们其中一次游戏的示例（空的洞用 `O` 表示，用石头盖住的洞用 `X` 表示）：

| 时间 | 洞 1 | 洞 2 | 洞 3 | 描述 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $0$ | O | O | O | 一开始所有的洞都是空的 |
| $1$ | O | O | X | 盖上洞 3 |
| $2$ | X | O | X | 盖上洞 1 |
| $3$ | X | O | O | 打开洞 3 |
| $4$ | X | X | O | 盖上洞 2 |
| $5$ | O | X | O | 打开洞 1 |
| $6$ | O | X | X | 盖上洞 3 |
| $7$ | X | X | X | 盖上洞 1 |

现在牛被卡住玩不下去了！他们必须打开一个洞，不管他们打开哪个洞，他们都会到达一个他们已经到达的状态。例如，如果他们从第二个洞中取出岩石，他们将到达他们在时间 $2$ 已经访问过的状态（`X O X`）。

下面是一个 3 个孔的有效解决方案：

| 时间 | 洞 1 | 洞 2 | 洞 3 | 描述 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $0$ | O | O | O | 一开始所有的洞都是空的 |
| $1$ | O | X | O | 盖上洞 2 |
| $2$ | O | X | X | 盖上洞 3 |
| $3$ | O | O | X | 打开洞 2 |
| $4$ | X | O | X | 盖上洞 1 |
| $5$ | X | X | X | 盖上洞 2 |
| $6$ | X | X | O | 打开洞 3 |
| $7$ | X | O | O | 打开洞 2 |
| $8$ | O | O | O | 打开洞 1，恢复到原来的状态 |

现在，奶牛们厌倦了这个游戏，它们想找你帮忙。

给定 $n$，求游戏的有效解决方案序列。如果有多个解决方案，则返回**任意一个**。

## 输入格式

仅一行，一个整数 $n$。

## 输出格式

共 $n$ 行，每行一个长度为 $n$ 的字符串，其中只包含字符 `O` 和 `X`，该行中的第 $i$ 个字符表示第 $i$ 个孔在此状态下是被覆盖还是未覆盖，第一行和最后一行必须全部都是 `O`。

## 样例 #1

### 样例输入 #1

```
3
```

### 样例输出 #1

```
OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO
```

## 提示

#### 样例 1 说明

见题目描述。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le15$。

【思路】

一道对思维很有挑战性的题，基本上就是直接套模板。

 【AC代码】

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int N=1e6+10;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
int n;
bool flag[N],a[N]={true},b[N][20];
void print()
{
	for(int i=1;i<=1<<n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(b[i][j])cout<<"X";
			else cout<<"O";
		}
		cout<<"\n";
	}
}
int check()//二进制转十进制
{
	int ans=0;
	for(int i=1;i<=n;i++)ans=ans*2+flag[i];//转进制核心
	return ans;
}
void dfs(int m)
{
	if(m==(1<<n))//经过观察，有几个孔就有2的几次方步，可以此为依据，写出这个if语句
	{
		print();
		exit(0);
	}
	for(int i=1;i<=n;i++)
	{
		flag[i]=!flag[i];//标记
		if(a[check()])//判断是否走过
		{
			flag[i]=!flag[i];//回溯
			 continue;//直接跳过
		}
		a[check()]=true;//记录为走过
		for(int j=1;j<=n;j++)b[m][j]=flag[j];//存储答案
		dfs(m+1),a[check()]=false,flag[i]=!flag[i];//继续搜索，回溯
	}
}
signed main()
{
	n=fread();
	for(int i=1;i<=n;i++)cout<<"O";
	cout<<"\n";
	dfs(1);//搜索
	return 0;
}

这题用搜索做有点复杂，看到一位不用dfs的，但是我现在练的就是dfs，还是用吧。 

给个关注吧