题目描述

题目分析

使用深度优先搜索(DFS),搜索所有 30 位的 0-1 字符串,判断 “11”(相邻的两台激光器同时打开)是否是其子字符串即可。
C++ 使用 s1.find(s2) == string::npos 判断 s2 是否是 s1 的子字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;

int ans;

void dfs(string s,int n) {
if(n==30) {
if(s.find("11")==string::npos) {
ans++;
}
return;
}
dfs(s+"0",n+1);
dfs(s+"1",n+1);
}

int main()
{
dfs("",0);
cout<<ans<<endl;

return 0;
}

题目答案

2178309