| ||||||||||
| 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