2802:小游戏利用bfs来实现

之前使用的是递归的方法来解决的问题，后来有点想用bfs(宽度优先搜索来尝试一下的想法，在网上看到有人使用了dfs(深度优先搜索）更加坚定了自己的这种想法。

这个方法首先是以顶点的四组开始，加入那些没有放置卡片的位置，同时使用另外一个数组来标记距离，就这样一直拓展下去，如果碰到了目标位置，那么我们就对totalStep进行对比赋值。

切记，每次搜索结束后，要对标记数组重新赋值，每个Board结束后，要对队列清空。

#include <bits/stdc++.h>

using namespace std;

class Node{

        //int direct,step;

    public:

        int x,y;

        Node(int x_,int y_):x(x_),y(y_){}

};

class directNode{

    public:

        int direct,step;

        directNode(int direct_,int step_):direct(direct_),step(step_){}

};

int w,h;

char s[][];

int  mark[][];

directNode * directStep[][];

int direction[][]={{-,},{,},{,},{,-}};

int totalStep=;

queue<Node *> ques;

void findTotalPath(int x1,int y1,int x2,int y2,int direct,int step){

    while(ques.size()>){

        Node * temp=ques.front();

        //cout<<temp->x<<"-"<<temp->y<<endl;

        if(temp->x==x2&&temp->y==y2){

            if(totalStep>directStep[temp->y][temp->x]->step&&directStep[temp->y][temp->x]->step!=){

                totalStep=directStep[temp->y][temp->x]->step;

                continue;

            }

        }

        for(int i=;i<;i++){

            int xx1=temp->x+direction[i][];

            int yy1=temp->y+direction[i][];

            if((xx1>-)&&(xx1<w+)&&(yy1>-)&&(yy1<h+)&&(s[yy1][xx1]==' '||(yy1==y2&&xx1==x2&&s[yy1][xx1]=='X'))){

                //cout<<"* "<<directStep[temp->y][temp->x]->step<<","<<directStep[temp->y][temp->x]->direct<<endl;

                int tempStep=directStep[temp->y][temp->x]->direct!=i?directStep[temp->y][temp->x]->step+:directStep[temp->y][temp->x]->step;

                if(mark[yy1][xx1]==){

                    if(directStep[yy1][xx1]->step>tempStep){

                        directStep[yy1][xx1]->direct=i;

                        directStep[yy1][xx1]->step=tempStep;

                    }

                }else{

                    ques.push(new Node(xx1,yy1));

                    directStep[yy1][xx1]->direct=i;

                    directStep[yy1][xx1]->step=tempStep;

                    mark[yy1][xx1]=;

                    //cout<<xx1<<" "<<yy1<<endl;

                    //cout<<"tempStep:"<<tempStep<<endl;

                }

            }

        }

        ques.pop();

    }

}

int main(){

    int id=;

    while(){

        /*cin>>w>>h;

        cin.ignore();*/

        scanf("%d %d",&w,&h);

        if(w==&&h==) break;

        /*for(int i=0;i<h+2;i++){

            s[i][0]=s[i][w+1]=' ';

        }

        for(int j=0;j<w+2;j++){

            s[0][j]=s[w+1][j]=' ';

        }*/

        for(int i=;i<h+;i++){

            for(int j=;j<w+;j++){

                directStep[i][j]=new directNode(-,);

            }

        }

        for (int i = ; i <; i ++) s[][i] =s[i][] = ' ';

        for(int i=;i<h+;i++){

            getchar();

            //string str="";

            //getline(cin,str);

            for(int j=;j<w+;j++){

                //s[i][j]=str[j-1];

                s[i][j]=getchar();

            }

        }

        for (int i = ; i <= w; i ++)

            s[h + ][i + ] = ' ';

        for (int i = ; i <= h; i ++)

            s[i + ][w + ] = ' ';

        cout<<"Board #"<<id<<":"<<endl;

        id++;

        int x1,y1,x2,y2;

        int subId=;

        while(){

            subId++;

             totalStep=;

             memset(mark, , sizeof(mark));

            cin>>x1>>y1>>x2>>y2;

            ques.push(new Node(x1,y1));

            mark[y1][x1]=;

            if(x1==&&y1==&&x2==&&y2==) break;

            int step=;

            int direct=-;

            findTotalPath(x1,y1,x2,y2,direct,step);

            if(totalStep<)

                cout<<"Pair "<<subId<<": "<<totalStep<<" segments."<<endl;

            else{

                cout<<"Pair "<<subId<<": "<<"impossible."<<endl;

            }

            for(int i=;i<h+;i++){

                for(int j=;j<w+;j++){

                    directStep[i][j]=new directNode(-,);

                }

        }

        }

        while(ques.size()>){

            ques.pop();

        }

        cout<<endl;

    }

}