題目描述
某寢室的同學們在學術完之后準備玩一個游戲： 游戲是這樣的，每個人頭上都被貼了一張白色或者黑色的紙，現(xiàn)在每個人都會說一句話“我看到x張白色紙條和y張黑色的紙條”，又已知每個頭上貼著白色紙的人 說的是真話、每個頭上貼著黑色紙的人說的是謊話，現(xiàn)在要求你判斷哪些人頭上貼著的是白色的紙條，如果無解輸出“NoSolution.”；如果有多組解， 則把每個答案中貼白條的人的編號按照大小排列后組成一個數(shù)（比如第一個人和第三個人頭上貼著的是白紙條，那么這個數(shù)就是13；如果第6、7、8個人都貼的 是白紙條，那么這個數(shù)就是678）輸出最小的那個數(shù)（如果全部都是黑紙條也滿足情況的話，那么輸出0）

數(shù)據(jù)規(guī)模和約定
n< =8
輸入
第一行為一個整數(shù)n，接下來n行中的第i行有兩個整數(shù)x和y，分別表示第i個人說“我看到x張白色紙條和y張黑色的紙條”。
輸出
一行。如果無解輸出“NoSolution.”。否則輸出答案中數(shù)值（具體見問題描述）最小的那個，如果全部都是黑紙條也滿足情況的話，那么輸出0
樣例輸入
5
3 1
0 4
1 3
4 0
1 3
樣例輸出
35
思路：深搜枚舉所有的答案，因為n最大只有8的數(shù)據(jù)量。然后判斷是否符合題意。
判斷條件如下：

if(vis[i]==1&&!(p[i].w==cnt-1&&p[i].b==n-cnt)) return 0; if(vis[i]==0&&p[i].w==cnt&&p[i].b==n-cnt-1) return 0;

代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=10; struct node{int b,w; }p[maxx]; int vis[maxx]; int n;inline bool check() {int cnt=0;for(int i=1;i<=n;i++) cnt+=vis[i];for(int i=1;i<=n;i++){if(vis[i]==1&&!(p[i].w==cnt-1&&p[i].b==n-cnt)) return 0;if(vis[i]==0&&p[i].w==cnt&&p[i].b==n-cnt-1) return 0;}return 1; } inline void dfs(int x,string &s) {if(x==n+1){if(check()){string t="";for(int i=1;i<=n;i++) if(vis[i]==1) t=t+(char)(i+'0');if(t=="") t="0";if(s=="") s=t;else s=min(s,t);}return ;}if(vis[x]==0){vis[x]=1;dfs(x+1,s);vis[x]=0;}dfs(x+1,s); } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&p[i].w,&p[i].b);memset(vis,0,sizeof(vis));string s="";dfs(1,s);if(s=="") cout<<"NoSolution."<<endl;else cout<<s<<endl;return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的[蓝桥杯][算法训练VIP]黑白无常（dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。