這道題用廣搜即可，只需要加兩個優化就行。。 代碼如下：

　　

/*ID: m1500293LANG: C++PROG: shuttle */ #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <string> #include <set> #include <iostream>using namespace std;struct State {string now, ans;State(string now="", string ans=""):now(now), ans(ans) {} };bool judge(int n, State st) {for(int i=0; i<n; i++)if(st.now[i]!='b') return false;if(st.now[n]!=' ') return false;for(int i=n+1; i<=n+1+n-1; i++)if(st.now[i]!='w') return false;return true; }set<string> vis; string bfs(int n) {queue<State> que;string now = "";for(int i=0; i<n; i++) now+='w';now+=' ';for(int i=0; i<n; i++) now+='b';que.push(State(now, ""));//cout<<now<<endl; vis.insert(now);while(!que.empty()){State tp = que.front(); que.pop();if(judge(n, tp)) return tp.ans;int idx = 0;for(int i=0; i<tp.now.length(); i++) if(tp.now[i]==' '){idx = i;break;}int len = tp.now.length();string str = tp.now;if(idx-2>=0 && str[idx-2]!=str[idx-1] && str[idx-2]=='w'){swap(str[idx-2], str[idx]);if(vis.find(str) == vis.end()){char c = '0'+idx-2;que.push(State(str, tp.ans+c));vis.insert(str);}swap(str[idx-2], str[idx]);}if(idx-1>=0 && str[idx-1]=='w'){swap(str[idx-1], str[idx]);if(vis.find(str) == vis.end()){char c = '0'+idx-1;que.push(State(str, tp.ans+c));vis.insert(str);}swap(str[idx-1], str[idx]);}if(idx+1 < len && str[idx+1]=='b'){swap(str[idx+1], str[idx]);if(vis.find(str) == vis.end()){char c = '0'+idx+1;que.push(State(str, tp.ans+c));vis.insert(str);}swap(str[idx+1], str[idx]);}if(idx+2<len && str[idx+2]!=str[idx+1] && str[idx+2]=='b'){swap(str[idx], str[idx+2]);if(vis.find(str) == vis.end()){char c = '0' + idx+2;que.push(State(str, tp.ans+c));vis.insert(str);}swap(str[idx], str[idx+2]);}}return ""; }int main() {freopen("shuttle.in", "r", stdin);freopen("shuttle.out", "w", stdout);int n;scanf("%d", &n);string s = bfs(n);int num = 0;for(int i=0; i<s.length(); i++){//printf("%c%c", s[i]+1, i==s.length()-1?'\n':' ');printf("%d", s[i]-'0'+1);num++;if(num==20){printf("\n");num = 0;}else if(i != s.length()-1)printf(" ");}if(s.length()%20!=0) printf("\n");return 0; }

?

轉載于:https://www.cnblogs.com/xingxing1024/p/5167623.html

總結

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

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