USACO Section 4.4 Shuttle Puzzle - Hash都不用的DFS水题..

网友投稿 253 2022-09-14

USACO Section 4.4 Shuttle Puzzle - Hash都不用的DFS水题..

龙年第一题~~~这题开始以为搜索会超时~~要用构造才行~~我这找了好久规律~~也没找出构造的方法~~~就写搜索了...

搜索的时候要注意方法和顺序...显然的是W只能往右移..B只能往左移~~否则不可能得到最小步数的解~~然后也能想到的其实只要每次都保证了W右移,B左移~~最小总步数一开始就是确定的...而如果在移的时候先尝试WB_ -> _BW...再尝试W_ -> _W 再尝试_B -> B_ 再尝试 _WB -> BW_ 这个顺序来找结果..那么最后得到的一定也是字典序最小的..这样来写..Hash是不需要的..因为不可能出现重复的情况...所以若DFS找到了第一组解~~就可以退出DFS了..这就是答案~~我这样子来搜结果...最大的输入数据20都能秒出~~~

Program:

/* ID: zzyzzy12 LANG: C++ TASK: shuttle*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std;int n,way[100005],num;string str,s; bool DFS(int p){ way[++num]=p; if (s==str) return true; if (p!=2 && s[p-1]=='B' && s[p-2]=='W') { s[p]='W'; s[p-2]=' '; if (DFS(p-2)) return true; s[p]=' '; s[p-2]='W'; } if (p!=1 && s[p-1]=='W') { s[p]='W'; s[p-1]=' '; if (DFS(p-1)) return true; s[p]=' '; s[p-1]='W'; } if (p!=n*2+1 && s[p+1]=='B') { s[p]='B'; s[p+1]=' '; if (DFS(p+1)) return true; s[p]=' '; s[p+1]='B'; } if (p!=n*2 && s[p+1]=='W' && s[p+2]=='B') { s[p]='B'; s[p+2]=' '; if (DFS(p+2)) return true; s[p]=' '; s[p+2]='B'; } num--; return false; } int main() { freopen("shuttle.in","r",stdin); freopen("shuttle.out","w",stdout); scanf("%d",&n); s=" "; int i; str=" "; for (i=1;i<=n;i++) { s+='W'; str+='B'; } s+=' '; str+=' '; for (i=1;i<=n;i++) { s+='B'; str+='W'; } num=-1; DFS(n+1); printf("%d",way[1]); for (i=2;i<=num;i++) { if (i%20==1) printf("\n%d",way[i]); else printf(" %d",way[i]); } printf("\n"); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据
上一篇:广告文案：才三个月，名媛下午茶的主题就跑偏了！
下一篇:我谈阶梯博弈( Staircase Nim )
相关文章

 发表评论

暂时没有评论，来抢沙发吧~