Before the cows head home for rest and recreation, Farmer John wantsthem to get some intellectual stimulation by playing a game.
The game board comprises N (1 <= N <= 15) identical holes in theground, all of which are initially empty. A cow moves by eithercovering exactly one hole with a rock, or uncovering exactly onepreviously covered hole. The game state is defined by which holesare covered with rocks and which aren't. The goal of the game isfor the cows to reach every possible game state exactly once andthen return to the state with all holes uncovered.The cows have been having a tough time winning the game. Below isan example of one of their games:
Holes
time 1 2 3
-----------------
0 O O O Initially all of the holes are empty
1 O O X The cow covers hole 3
2 X O X The cow covers hole 1
3 X O O The cow uncovers hole 3
4 X X O The cow covers hole 2
5 O X O The cow uncovers hole 1
6 O X X The cow covers hole 3
7 X X X The cow covers hole 1
Now the cows are stuck! They must uncover one hole and no matterwhich one they uncover they will reach a state they have alreadyreached. For example if they remove the rock from the second hole they will reach the state (X O X) which they already visited at
time 2.
Below is an example of a valid solution for N=3 holes:
Holes
time 1 2 3
-----------------
0 O O O Initial state: all of the holes are empty
1 O X O The cow covers hole 2
2 O X X The cow covers hole 3
3 O O X The cow uncovers hole 2
4 X O X The cow covers hole 1
5 X X X The cow covers hole 2
6 X X O The cow uncovers hole 3
7 X O O The cow uncovers hole 2
8 O O O The cow uncovers the 1st hole
which returns the game board to the start having, visited each state once.
The cows are tired of the game and want your help. Given N, create a valid sequence of states that solves the game. If there are multiple solutions return any one.
PROBLEM NAME: rocks
INPUT FORMAT:
* Line 1: A single integer: N
SAMPLE INPUT (file rocks.in):
3
OUTPUT FORMAT:
* Lines 1..2^N+1: A string of length N containing only 'O' and 'X' (where O denotes a uncovered hole and X denotes a covered hole). The jth character in this line represents whether the jth hole is covered or uncovered in this state. The first and last lines must be all uncovered (all O).
SAMPLE OUTPUT (file rocks.out):
OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO
题目大意就是写出长度为n的X和O的所有排列，其中相邻的两个排列之间只能有一个数不同。
因为数据不是很大最多有2 ^ 15种排列，所以dfs就行。
只要每一次改变其中一个数，然后判断这种排列前面是否已经存在过，不存在就输出。
但每一次判断的时候是一个字符串，无论是空间上还是时间上都不是很好。于是有一个优化：吧‘O’看成0，'X'看成1，于是就变成了一个01串，即一个数的二进制。
于是我们只要尝试修改这个数的每一位，然后判断得到的新的数是否存在过就行。
至于修改，当然是亦或号啦
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cctype> //isdigit
using namespace std;
typedef long long ll;
#define enter printf("\n")
const int maxn = 1e6 + ;
const int INF = 0x3f3f3f3f;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch))
{
ans = ans * + ch - ''; ch = getchar();
}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) {putchar('-'); x = -x;}
if(x == ) {putchar(''); return;}
int q[], N = ;
q[] = ;
while(x) {q[++N] = x % ; x /= ;}
while(N) {putchar('' + q[N]); --N;}
} int n;
bool vis[maxn];
void print(int x) //从高位开始输出每一位
{
vis[x] = ;
for(int i = n - ; i >= ; --i)
{
if((x >> i) & ) printf("X");
else printf("O");
}
enter;
}
void dfs(int step, int x)
{
if(!vis[x]) print(x); //之所以放在这，而不是第53行之后，是为了输出最开始的OOOOOOO情况
if(step == ( << n) + ) exit();
for(int i = ; i <= n - ; ++i)
{
int now = x ^ ( << i);
if(!vis[now]) dfs(step + , now);
}
} int main()
{
n = read();
dfs(, );
for(int i = ; i <= n; ++i) printf("O"); enter;
return ;
}