当前位置:网站首页>P6183 [USACO10MAR] The Rock Game S
P6183 [USACO10MAR] The Rock Game S
2022-07-05 15:03:00 【A program ape who beats the keyboard violently】
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 .
边栏推荐
- 启牛证券账户怎么开通,开户安全吗?
- CPU设计实战-第四章实践任务二用阻塞技术解决相关引发的冲突
- CPU design related notes
- Talk about your understanding of microservices (PHP interview theory question)
- js亮瞎你眼的日期选择器
- 【数组和进阶指针经典笔试题12道】这些题,满足你对数组和指针的所有幻想,come on !
- Want to ask the big guy, is there any synchronization from Tencent cloud Mysql to other places? Binlog saved by Tencent cloud MySQL on cos
- webRTC SDP mslabel lable
- 长列表优化虚拟滚动
- B站做短视频,学抖音死,学YouTube生?
猜你喜欢
随机推荐
P6183 [USACO10MAR] The Rock Game S
可转债打新在哪里操作开户是更安全可靠的呢
Stm32+bh1750 photosensitive sensor obtains light intensity
easyOCR 字符识别
想进阿里必须啃透的12道MySQL面试题
超级哇塞的快排,你值得学会!
Using tensorboard to visualize the training process in pytoch
CPU design related notes
Photoshop plug-in - action related concepts - actions in non loaded execution action files - PS plug-in development
Leetcode: Shortest Word Distance II
Selection and use of bceloss, crossentropyloss, sigmoid, etc. in pytorch classification
729. My schedule I: "simulation" & "line segment tree (dynamic open point) &" block + bit operation (bucket Division) "
PostgreSQL 13 installation
729. 我的日程安排表 I :「模拟」&「线段树(动态开点)」&「分块 + 位运算(分桶)」
Ctfshow web entry explosion
CODING DevSecOps 助力金融企业跑出数字加速度
Cartoon: programmers don't repair computers!
我想咨询一下,mysql一个事务对于多张表的更新,怎么保证数据一致性的?
Leetcode: Shortest Word Distance II
FR练习题目---简单题