首页 > 代码库 > poj 2243 bfs 利用 结构体中的step成员保存步数 ,STL的队列

poj 2243 bfs 利用 结构体中的step成员保存步数 ,STL的队列

//BFS#include <iostream>#include <queue>using namespace std;bool used[8][8];int move[8][2]={1,2, -1,2, -2,1, -2,-1, -1,-2, 1,-2, 2,-1, 2,1};struct position{    int i,j;    int step;    position(int a,int b,int c)    {        i=a;        j=b;        step=c;    }};int main(){    char a[2],b[2];    int bi,bj,ei,ej,i;    while (cin>>a>>b)    {        bi=a[0]-a;        bj=a[1]-1;        ei=b[0]-a;        ej=b[1]-1;        memset(used,false,sizeof(used));        queue<position> myqueue;        position temp(bi,bj,0),now(0,0,0);        myqueue.push(temp);        used[bi][bj]=true;        while (myqueue.empty()==false)        {            temp=myqueue.front();            myqueue.pop();            if (temp.i==ei && temp.j==ej)                break;            for (i=0;i<8;i++)            {                now.i=temp.i+move[i][0];                now.j=temp.j+move[i][1];                if (now.i>=0 && now.i<8 && now.j>=0 && now.j<8 && used[now.i][now.j]==false)                {                    now.step=temp.step+1;                    used[now.i][now.j]=true;                    myqueue.push(now);                }            }        }        cout<<"To get from "<<a<<" to "<<b<<" takes "<<temp.step<<" knight moves."<<endl;    }    return 0;}

 

 

 

//BFS


#include <iostream>
#include <queue>
using namespace std;
bool used[8][8];
int move[8][2]={1,2, -1,2, -2,1, -2,-1, -1,-2, 1,-2, 2,-1, 2,1};
struct position
{
    int i,j;
    int step;
 
};
int main()
{
    char a[2],b[2];
    int bi,bj,ei,ej,i;
    while (cin>>a>>b)
    {
        bi=a[0]-‘a‘;
        bj=a[1]-‘1‘;
        ei=b[0]-‘a‘;
        ej=b[1]-‘1‘;
        memset(used,false,sizeof(used));
        queue<position> myqueue;
        struct position temp,now;
    temp.i=bi;  temp.j=bj; temp.step=0;
     now.i=0;  now.j=0; now.step=0;
       
       
        
          
        myqueue.push(temp);
        used[bi][bj]=true;
        while (myqueue.empty()==false)
        {
            temp=myqueue.front();
            myqueue.pop();
            if (temp.i==ei && temp.j==ej)
                break;
            for (i=0;i<8;i++)
            {
                now.i=temp.i+move[i][0];
                now.j=temp.j+move[i][1];
                if (now.i>=0 && now.i<8 && now.j>=0 && now.j<8 && used[now.i][now.j]==false)
                {
                    now.step=temp.step+1;
                    used[now.i][now.j]=true;
                    myqueue.push(now);
                }
            }
        }
        cout<<"To get from "<<a<<" to "<<b<<" takes "<<temp.step<<" knight moves."<<endl;
    }
    return 0;
}