排排坐

題目大意：

有n個方塊，有一些是黑色，有一些是白色，可以點擊一個方塊使它和它旁邊的方塊反轉顏色（黑變白，白變黑），問最少要點多少次才能將方塊 們 變成目標的方塊們，如果不行，輸出"Boring"

原題：

題目描述

小B喜歡在藍心網玩游戲,一天他玩到了這個游戲:他感覺非常好玩…于是他就YY出了一個類似的簡易模型…
游戲規則：每次點擊一個小朋友，他和他的周圍的小朋友都會改變狀態（蹲下的變成了站起來的，站起來的變成了蹲下的）
我們將這個抽象成如下圖所示的1*N的圖.對于一個單元格,黑色表示小朋友是站起來的,反之,蹲下的小朋友是是白色的.Source表示初始狀態,Target表示目標狀態.

現在小B有點偷懶,希望作為神牛的你幫小B算出初始狀態到目標狀態的最少點擊數.

輸入

第一行為N表示小朋友的個數.
第二行是初始狀態,有N個數,每個數不是0就是1.(0表示小朋友是蹲下的,1表示小朋友是站起來的)
第三行的結構跟第二行類似,表示目標狀態

輸出

一個數X,表示初始狀態到目標狀態的最少點擊數。
如果無法到達目標,則請輸出"Boring"

輸入樣例

9 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0

輸出樣例

2

只需要點擊第二個和第六個點即可。

說明

對于100%的數據，N<=10

解題思路：

枚舉每一個方塊，看點不點，就是O（$2^{10}$），然后判斷，求最小即可

代碼：

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,t,ans,a[15],b[15]; void dfs(int dep,int now) {if (dep>n)//已完成{t=0;//清零for (int i=1;i<=n;++i)if (a[i]!=b[i]) t=1;//有一個不同就不行if (!t) ans=min(ans,now);//取最小值return;}if (now>=ans) return;a[dep-1]=(a[dep-1]+1)%2;//翻a[dep]=(a[dep]+1)%2;a[dep+1]=(a[dep+1]+1)%2;dfs(dep+1,now+1);a[dep-1]=(a[dep-1]+1)%2;//返回去a[dep]=(a[dep]+1)%2;a[dep+1]=(a[dep+1]+1)%2;dfs(dep+1,now); } int main() {scanf("%d",&n);for (int i=1;i<=n;++i)scanf("%d",&a[i]);for (int i=1;i<=n;++i)scanf("%d",&b[i]);ans=2147483647;dfs(1,0);printf("%d",ans);//輸出 }

總結

以上是生活随笔為你收集整理的【DFS】排排坐的全部內容，希望文章能夠幫你解決所遇到的問題。

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