首页 > 代码库 > HDU 1195 Open the Lock
HDU 1195 Open the Lock
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1195
思路：广搜~ 。。 我用的双向广搜优化的。。。
发现了一个非常好的双向bfs的模板
//双向广搜代码框架 struct State { }; //状态 queue<State>que[2]; bool vis[2]; bool flag; void bfs(int d) { int size=que[d].size(); while(size--) { //普通单广转移新状态v if(vis[d][v]) continue; if(vis[d^1][v]) { flag=true; return; } //新状态入队 } } int dbfs() { //初始化 int cnt=0; while(true) { cnt++; if(que[0].size()<que[1].size()) bfs(0); else bfs(1); if(flag) break; } return cnt; }
照着这个来，然后 就A了， 双向广搜果然比普通的bfs省时间。
#include <iostream>#include <queue>#include <string>#include <cstdio>#include <cstring>#include <map>using namespace std;string end;string start;struct node{ string a;};queue<node> q[2];bool mark[2][10][10][10][10];int flag;void bfs(int c);int dbfs() { //初始化 while(!q[0].empty()) q[0].pop(); while(!q[1].empty()) q[1].pop(); memset(mark, false, sizeof(mark)); node t = {start}; q[0].push(t); t.a = end; q[1].push(t); flag = 0; int cnt=0; while(true) { cnt++; if(q[0].size()<q[1].size()) bfs(0); else bfs(1); if(flag==1) break; } return cnt; }void bfs(int c){ int size = q[c].size(); while(size --) { node temp = q[c].front(); q[c].pop(); if(mark[c][temp.a[0]-‘0‘][temp.a[1]-‘0‘][temp.a[2]-‘0‘][temp.a[3]-‘0‘]) { continue; } if(mark[c^1][temp.a[0]-‘0‘][temp.a[1]-‘0‘][temp.a[2]-‘0‘][temp.a[3]-‘0‘]) { flag = 1; return; } node t2; for( int i = 0; i < 3; i++) { t2.a = temp.a; char t = t2.a[i]; t2.a[i] = t2.a[i+1]; t2.a[i+1] = t; q[c].push(t2); } for( int i =0; i<4; i++) { t2.a = temp.a; t2.a[i]++; if(t2.a[i] == ‘9‘+1) t2.a[i] = ‘1‘; q[c].push(t2); } for( int i =0; i<4; i++) { t2.a = temp.a; t2.a[i]--; if(t2.a[i] == ‘1‘ - 1) t2.a[i] = ‘9‘; q[c].push(t2); } mark[c][temp.a[0]-‘0‘][temp.a[1]-‘0‘][temp.a[2]-‘0‘][temp.a[3]-‘0‘] = true; }}int main(){ int num; cin>>num; while(num--) { cin>>start; cin>>end; cout<<dbfs()-2<<endl; } return 0;}
HDU 1195 Open the Lock
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。