Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:3278 已解决In Reply To:3278 已解决 Posted by:zsc08_hyq at 2009-11-22 13:13:32 #include <iostream> #include <queue> using namespace std; struct Node { //public: int location; int sum; Node(int L=0,int S=0) { location=L; sum=S; } }; Node temp; bool flag[100001]; queue<Node> Q; int Bfs ( int start, int end ) { Node f; f.location = start; f.sum = 0; Q.push(f); while ( !Q.empty() ) { //-----------结束条件----------- if (Q.front().location==end) return Q.front().sum;//----------------- temp = Q.front(); //--------对邻接的三种操作入队--------- Node f1,f2,f3; f1.location=temp.location*2; f2.location=temp.location+1; f3.location=temp.location-1; f1.sum=temp.sum+1; f2.sum=temp.sum+1; f3.sum=temp.sum+1; /* Q.push (f1); Q.push (f2); Q.push (f3); Q.push(Node(Q.front().location+1,Q.front().sum+1)) */ //-------------------- if(f1.location<100001 && f1.location>=0 ) { if(flag[f1.location]==false) { Q.push (f1); flag[f1.location]=true; } } if(f3.location<100001 && f3.location>=0 ) { if(flag[f3.location]==false) { Q.push (f3); flag[f3.location]=true; } } if(f2.location<100001 && f2.location>=0 ) { if(flag[f2.location]==false) { Q.push (f2); flag[f2.location]=true; } } Q.pop(); } } int main () { int s,e; while ( cin >> s >> e ) { while(!Q.empty()) Q.pop(); memset(flag,false,sizeof flag); flag[s]=true; cout << Bfs ( s, e ) << endl; } //system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator