P6183 [USACO10MAR] The Rock Game S

Program ape kills CSDN Force list , ranking 31！！！

 

P6183 [USACO10MAR] The Rock Game S

# [USACO10MAR] The Rock Game S

## Title Description

Before the cows go home for rest and recreation ,Farmer John I hope they can get some intellectual stimulation by playing games . Game board by $n$ Composed of the same holes , These holes were originally ** Are empty **. A cow either covers a hole with a stone , Or uncover a previously covered hole .** Game status ** The definition of is which holes are covered by stones , Which holes are not covered . The goal of the game is to make the cow accurately reach every possible game state once , Then return to the state that all holes are not covered . Here is an example of one of their games （ Empty holes are used `O` Express , The hole covered with stone is used `X` Express ）：

| Time | hole 1 | hole 2 | hole 3 | describe |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $0$ | O | O | O | At first all the holes were empty |
| $1$ | O | O | X | Cover the hole 3 |
| $2$ | X | O | X | Cover the hole 1 |
| $3$ | X | O | O | Open the hole 3 |
| $4$ | X | X | O | Cover the hole 2 |
| $5$ | O | X | O | Open the hole 1 |
| $6$ | O | X | X | Cover the hole 3 |
| $7$ | X | X | X | Cover the hole 1 |

Now the cow is stuck and can't play anymore ！ They have to open a hole , No matter which hole they open , They will all reach the state they have reached . for example , If they take the rock out of the second hole , They will arrive at their time $2$ Status that has been accessed （`X O X`）.

Here's a 3 An effective solution for holes ：

| Time | hole 1 | hole 2 | hole 3 | describe |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $0$ | O | O | O | At first all the holes were empty |
| $1$ | O | X | O | Cover the hole 2 |
| $2$ | O | X | X | Cover the hole 3 |
| $3$ | O | O | X | Open the hole 2 |
| $4$ | X | O | X | Cover the hole 1 |
| $5$ | X | X | X | Cover the hole 2 |
| $6$ | X | X | O | Open the hole 3 |
| $7$ | X | O | O | Open the hole 2 |
| $8$ | O | O | O | Open the hole 1, Return to the original state |

Now? , Cows are tired of this game , They want to ask you for help .

Given $n$, Find an effective solution sequence for the game . If there are multiple solutions , Then return to ** Any one **.

## Input format

Just one line , An integer $n$.

## Output format

common $n$ That's ok , One length per line is $n$ String , It contains only characters `O` and `X`, The... In this line $i$ The first character represents the second $i$ Are the holes covered or not covered in this state , The first and last lines must all be `O`.

## Examples #1

### The sample input #1

```
3
```

### Sample output #1

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

## Tips

#### Examples 1 explain

See Title Description .

#### Data scale and agreement

about $100\%$ The data of , Yes $1\le n\le15$.

【 Ideas 】

Together, we are very good at thinking challenging The topic , Basically It's direct Set of templates .

 【AC Code 】

#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()// Binary to decimal 
{
	int ans=0;
	for(int i=1;i<=n;i++)ans=ans*2+flag[i];// Conversion core 
	return ans;
}
void dfs(int m)
{
	if(m==(1<<n))// After observation , There are several holes 2 Several square steps , That's the basis , Write this if sentence 
	{
		print();
		exit(0);
	}
	for(int i=1;i<=n;i++)
	{
		flag[i]=!flag[i];// Mark 
		if(a[check()])// Judge whether you have passed 
		{
			flag[i]=!flag[i];// to flash back 
			 continue;// Just skip 
		}
		a[check()]=true;// Record as walking 
		for(int j=1;j<=n;j++)b[m][j]=flag[j];// Store answers 
		dfs(m+1),a[check()]=false,flag[i]=!flag[i];// Continue to search , to flash back 
	}
}
signed main()
{
	n=fread();
	for(int i=1;i<=n;i++)cout<<"O";
	cout<<"\n";
	dfs(1);// Search for 
	return 0;
}

It's a little complicated to use search , See a person who doesn't need dfs Of , But what I practice now is dfs, Let's use it . 

Pay attention to it