自己做的网站别人,怎么做精准引流推广,河间网站制作公司,珠海网站建设哪家专业题目描述
在奶牛回家休息和娱乐之前#xff0c;Farmer John 希望它们通过玩游戏获得一些智力上的刺激。游戏板由 n 个相同的孔组成#xff0c;这些孔最初都是空的。一头母牛要么用石头盖住一个洞#xff0c;要么揭开一个先前被盖住的洞。游戏状态的定义是哪些洞被石头覆盖Farmer John 希望它们通过玩游戏获得一些智力上的刺激。游戏板由 n 个相同的孔组成这些孔最初都是空的。一头母牛要么用石头盖住一个洞要么揭开一个先前被盖住的洞。游戏状态的定义是哪些洞被石头覆盖哪些洞没有覆盖。游戏的目标是让奶牛准确地到达每个可能的游戏状态一次然后返回到所有洞都没有覆盖的状态。以下是他们其中一次游戏的示例空的洞用 O 表示用石头盖住的洞用 X 表示
时间洞 1洞 2洞 3描述00OOO一开始所有的洞都是空的11OOX盖上洞 322XOX盖上洞 133XOO打开洞 344XXO盖上洞 255OXO打开洞 166OXX盖上洞 377XXX盖上洞 1
现在牛被卡住玩不下去了他们必须打开一个洞不管他们打开哪个洞他们都会到达一个他们已经到达的状态。例如如果他们从第二个洞中取出岩石他们将到达他们在时间 22 已经访问过的状态X O X。
下面是一个 3 个孔的有效解决方案
时间洞 1洞 2洞 3描述00OOO一开始所有的洞都是空的11OXO盖上洞 222OXX盖上洞 333OOX打开洞 244XOX盖上洞 155XXX盖上洞 266XXO打开洞 377XOO打开洞 288OOO打开洞 1恢复到原来的状态
现在奶牛们厌倦了这个游戏它们想找你帮忙。
给定 n求游戏的有效解决方案序列。如果有多个解决方案则返回任意一个。
输入格式
仅一行一个整数 n。
输出格式
共 2n1 行每行一个长度为 n 的字符串其中只包含字符 O 和 X该行中的第 i 个字符表示第 i 个孔在此状态下是被覆盖还是未覆盖第一行和最后一行必须全部都是 O。
输入输出样例
输入
3
输出
OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO
说明/提示
样例 1 说明
见题目描述。
数据规模与约定
对于 100% 的数据有 1≤n≤15。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int M4e410;
const int N1e610;
int n;
bool flag[N],a[N]{false},b[N][20];
int check()
{int ans0;for(int i1;in;i){ansans*2flag[i];}return ans;
}
void dfs(int step)
{if(step(1n)){for(int i1;i(1n);i){for(int j1;jn;j){if(b[i][j])coutX;elsecoutO;}coutendl;}exit(0);}for(int i1;in;i)//尝试每一个点作为改变的起点{flag[i]!flag[i];if(a[check()])//如果已经出现过则代表此点被改变后的所有情况都出现过所以直接跳过{flag[i]!flag[i];continue;}a[check()]true;for(int j1;jn;j) b[step][j]flag[j];dfs(step1);flag[i]!flag[i];//尝试下一个点将此点变为原样 }
}
void solve()
{cinn;for(int i1;in;i) coutO;//先输出coutendl;a[check()]true;//将第一种情况直接设置为已经走过dfs(1);return ;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t1;
// cint;while(t--){ solve();}return 0;
}
