藍橋杯dfs搜索專題
2018激光樣式
題目描述
x星球的盛大節日為增加氣氛，用30台機光器一字排開，向太空中打出光柱。
安裝調試的時候才發現，不知什麼原因，相鄰的兩台激光器不能同時打開！
國王很想知道，在目前這種bug存在的情況下，一共能打出多少種激光效果？
顯然，如果只有3台機器，一共可以成5種樣式，即：
全都關上（sorry, 此時無聲勝有聲，這也算一種）
開一台，共3種
開兩台，只1種
30台就不好算了，國王只好請你幫忙了。
輸出
輸出一個整數表示答案
動態規劃
#include<bits/stdc++.h>
using namespace std;
int main() {
//freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n = 30, a[31] = { 0,2,3 };
//類似斐波那契數列的遞推
for (int i = 3; i <= n; ++i)a[i] = a[i - 1] + a[i - 2];
cout << a[n];
}
//2178309
DFS搜索
#include<bits/stdc++.h>
using namespace std;
int cnt = 0,n = 30;
bool vis[40];
/*
dfs(i) 第i個激光機器 有兩種選擇:vis[i-1] == 0 時 可選,無論vis[i-1]為何值都不選
vis[i] 回溯標記是否用過
*/
void dfs(int x) {
if (x == n + 1) { cnt++; return; }
dfs(x + 1);
if (vis[x - 1] == 0) {
vis[x] = 1;
dfs(x + 1);
vis[x] = 0;
}
}
int main() {
//freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for (int i = 0; i <= 30; ++i)vis[i] = 0;
dfs(1); cout << cnt << endl;
}
//2178309
2017磁磚樣式
小明家的一面裝飾牆原來是 3*10 的小方格。
現在手頭有一批剛好能蓋住2個小方格的長方形瓷磚。
瓷磚只有兩種顏色：黃色和橙色。
小明想知道，對於這麼簡陋的原料，可以貼出多少種不同的花樣來。
小明有個小小的強迫症：忍受不了任何2*2的小格子是同一種顏色。
（瓷磚不能切割，不能重疊，也不能只鋪一部分。另外，只考慮組合圖案，請忽略瓷磚的拼縫）
顯然，對於 2*3 個小格子來說，口算都可以知道：一共10種貼法，如【p1.png所示】
但對於 3*10 的格子呢？肯定是個不小的數目，請你利用計算機的威力算出該數字。
注意：你需要提交的是一個整數，不要填寫任何多餘的內容（比如：說明性文字）
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 10;
int g[maxn][maxn];
vector<int> v;
set<vector<int> > se;
set<vector<int> > se2;
map<int, int> Hash;
int ans = 0;
bool check_color() {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if(i+1 <= n && j+1 <= m) {
//1 1 1 1 2 2 2 2 1 2 1 2
if((g[i][j]+g[i][j+1]+g[i+1][j]+g[i+1][j+1]) % 4 == 0)
return false;
}
}
return true;
}
bool check2(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j] == 0){
return false;
}
}
}
for(int i=1;i<=n-1;i++){
for(int j=1;j<=m-1;j++){
int aa = g[i][j];
int bb = g[i+1][j];
int cc = g[i][j+1];
int dd = g[i+1][j+1];
if(aa == bb && aa ==cc && bb== cc && cc == dd && bb == dd && aa == dd){
return false;
}
}
}
return true;
}
bool check(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j] == 0){
return false;
}
}
}
for(int i=1;i<=n-1;i++){
for(int j=1;j<=m-1;j++){
if(g[i][j] == g[i+1][j] == g[i][j+1] == g[i+1][j+1])
return false;
}
}
return true;
}
void dfs(int x,int y){
if(x == n+1 && y == 1){
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<g[i][j]<<" ";
// }
// cout<<endl;
// }
if(check_color()){
v.clear();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
v.push_back(g[i][j]);
}
}
se.insert(v);
}
if(check2()){
v.clear();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
v.push_back(g[i][j]);
}
}
se2.insert(v);
}
return;
}
if(g[x][y]){
if(y == m)
dfs(x+1,1);
else
dfs(x,y+1);
}else{
if(y+1 <= m && !g[x][y+1]){
for(int i=1;i<=2;i++){
g[x][y+1] = i;
g[x][y] = i;
if(y == m){
dfs(x+1,1);
}else{
dfs(x,y+1);
}
g[x][y] = 0;
g[x][y+1] = 0;
}
}
if(x+1 <= n && !g[x+1][y]){
for(int i=1;i<=2;i++){
g[x+1][y] = i;
g[x][y] = i;
if(y == m){
dfs(x+1,1);
}else{
dfs(x,y+1);
}
g[x+1][y] = 0;
g[x][y] = 0;
}
}
}
}
int main(){
n = 3, m =10;
dfs(1,1);
cout<<se2.size()<<endl;
cout<<se.size()<<endl;
set<vector<int> >::iterator it = se2.begin();
vector<int> vv;
while(it != se2.end()){
if(se2.find(*it) != se2.end() && se.find(*it) == se.end() ){
vv = *it;
break;
}
it++;
}
int t = 0;
for(int i=0;i<vv.size();i++){
if(t == 10) {
t = 0;
cout<<endl;
}
cout<<vv[i]<<" ";
t++;
}
cout<<endl;
return 0;
}
//123996我的答案 check函數 是錯的？！！ check2函數是對的
//101466網上答案 是對的！！
//原因:檢查顏色的函數出錯 為什麼? 不能連等判斷。。。。。這語法
//已改正
/*
1 1 1 1 1 1 1 1 1 1
1 2 1 2 2 1 2 2 1 2
1 2 2 2 2 2 1 1 1 2
*/
2016湊平方數
把0~9這10個數字，分成多個組，每個組恰好是一個平方數，這是能夠辦到的。 比如：0, 36, 5948721
再比如： 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等…
注意，0可以作為獨立的數字，但不能作為多位數字的開始。 分組時，必須用完所有的數字，不能重複，不能遺漏。
如果不計較小組內數據的先後順序，請問有多少種不同的分組方案？
注意：需要提交的是一個整數，不要填寫多餘內容。
思路：
用到了STL裏面的排列組合算法
next_permutation()返回的是一個布爾值，並且在內部已經把一個數組的順序或者一個string的順序改變了
然後利用set有去重的特性來插入
枚舉所有可能的情況搜索即可
答案：300
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
ll nums[10];
set<string> res;
//判斷一個是否為平方數
bool isqnum(long long num) {
double d = sqrt(num);
return d == (long long)d;
}
//從arr:[i, n)尋找平方數
void dfs(int i, int n) {
if (i == 10) {
ll nums_t[10];
copy(nums, nums + n, nums_t);
sort(nums_t, nums_t + n);
string s;
for (int j = 0; j < n; ++j) {
s += to_string(nums_t[j]) + ',';
}
res.insert(s);
return;
}
if (arr[i] == 0) {
nums[n] = 0;
dfs(i + 1, n + 1);
return;
}
long long num = 0;
for (int j = i; j < 10; ++j) {
num = num * 10 + arr[j];
if (isqnum(num)) {
nums[n] = num;
dfs(j + 1, n + 1);
}
}
}
int main() {
do {
dfs(0, 0);
} while (next_permutation(arr, arr + 10));
cout << res.size() << endl;
return 0;
}
2015完美正方形
#include<bits/stdc++.h>
using namespace std;
int n = 47 + 46 + 61;//邊長
int a[19] = { 2, 5, 9, 11, 16, 17, 19, 21, 22, 24, 26, 30, 31, 33, 35, 36, 41, 50, 52 };
int g[500][500];//大正方形地圖
int vis[30];
set<int> se;//集合存儲正方形最後一行邊長數據結果
void fill(int x, int y, int l, int num) {
for (int i = x; i <= x + l - 1; i++) {
for (int j = y; j <= y + l - 1; j++) {
g[i][j] = num;
}
}
}
bool ok(int x, int y, int l) {
if (x + l - 1 > n) return false;
if (y + l - 1 > n) return false;
for (int i = x; i <= x + l - 1; i++) {
for (int j = y; j <= y + l - 1; j++) {
if (g[i][j] != 0) return false;
}
}
return true;
}
bool check() {
return true;
}
void dfs(int x, int y) {
if (x == n + 1) {//遞歸出口
if (check()) {
for (int i = 1; i <= n; i++) {
se.insert(g[n][i]);//set集合存儲最後一層正方形邊長數據
}
}
return;
}
if (g[x][y] != 0) {//當前正方形填充過了
if (y == n)
dfs(x + 1, 1);//dfs下一個
else
dfs(x, y + 1);//dfs下一個
}
else {//當前正方形沒有填充過
for (int i = 0; i < 19; i++) {//枚舉19塊正方形
if (!vis[i]) {
if (ok(x, y, a[i])) {
fill(x, y, a[i], a[i]);//填充正方形成a[i]邊長 以(x,y)為左上頂點
vis[i] = 1;
if (y == n) {
dfs(x + 1, 1);//dfs下一個
}
else {
dfs(x, y + 1);//dfs下一個
}
vis[i] = 0;//回溯
fill(x, y, a[i], 0);//填充正方形成0 以(x,y)為左上頂點
}
else {
break;//剪枝 因為a數組按順序排的 當前邊長不行 後面邊長更不行了
}
}
}
}
}
int main() {
fill(1, 1, 47, 47);//填充以(1,1)為左上頂點的正方形 邊為47
fill(1, 47 + 1, 46, 46);
fill(1, 47 + 46 + 1, 61, 61);
dfs(1, 1);//從(1,1)點開始搜索
set<int>::iterator it = se.begin();
while (it != se.end()) {
cout << *it << " ";
it++;
}
return 0;
}
//30 33 41 50
