思路:DFS寻找
当时写的没思路,睡觉去了,靠着两个队友一直对拍过的,主要考虑num=7的情况
#include<bits/stdc++.h>
using namespace std;
int a[10];
bool ans = false;
int num = 0;
void DFS()
{
for (int i = 1; i <= 8; i++)
{
if(a[i]==0) //当前位置未放置硬币,分别分析第(i+2)%8+1和a[(i+4)%8+1个位置
{
if(a[(i+2)%8+1]==0)
{
a[i] = 1;
num++;
if (num == 7)
{
ans = true; //标记
return;
}
DFS();
if (num == 7)
return;
a[i] = 0; //回溯
num--;
}
if(a[(i+4)%8+1]==0)
{
a[i] = 1;
num++;
if (num == 7)
{
ans = true;
return;
}
DFS();
if (num == 7)
return;
a[i] = 0;
num--;
}
}
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
string s; //字符串
num = 0;
ans = false;
cin >> s;
for (int i = 1; i <= 8; i++)
{
a[i] = s[i - 1] - '0'; //将字符串转化成数字型数组
if (a[i] == 1) //若当前位置放置了硬币
num++; //num加一
}
if (num == 7)
cout << "Yes" << endl; //当满足题目条件时,放满七个输出Yes
else
{
DFS(); //深度查找
cout << (ans ? "Yes" : "No") << endl; //判断输出
}
}
return 0;
}