欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2802:小游戏利用bfs来实现

程序员文章站 2023-03-09 13:04:59
之前使用的是递归的方法来解决的问题,后来有点想用bfs(宽度优先搜索来尝试一下的想法,在网上看到有人使用了dfs(深度优先搜索)更加坚定了自己的这种想法。 这个方法首先是以顶点的四组开始,加入那些没有放置卡片的位置,同时使用另外一个数组来标记距离,就这样一直拓展下去,如果碰到了目标位置,那么我们就对 ......

之前使用的是递归的方法来解决的问题,后来有点想用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[100][100];
int  mark[100][100];
directNode * directStep[100][100];
int direction[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int totalStep=100000;
queue<Node *> ques;
void findTotalPath(int x1,int y1,int x2,int y2,int direct,int step){
    while(ques.size()>0){
        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!=0){
                totalStep=directStep[temp->y][temp->x]->step;
                continue;
            }
        }
        for(int i=0;i<4;i++){
            int xx1=temp->x+direction[i][1];
            int yy1=temp->y+direction[i][0];
            if((xx1>-1)&&(xx1<w+2)&&(yy1>-1)&&(yy1<h+2)&&(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+1:directStep[temp->y][temp->x]->step;
                if(mark[yy1][xx1]==1){
                    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]=1;
                    //cout<<xx1<<" "<<yy1<<endl;
                    //cout<<"tempStep:"<<tempStep<<endl;
                }
            }
        }
        ques.pop();
    }
}
int main(){
    int id=1;
    while(1){
        /*cin>>w>>h;
        cin.ignore();*/
        scanf("%d %d",&w,&h);
        if(w==0&&h==0) 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=0;i<h+2;i++){
            for(int j=0;j<w+2;j++){
                directStep[i][j]=new directNode(-1,0);
            }
        }
        for (int i = 0; i <100; i ++) s[0][i] =s[i][0] = ' ';
        for(int i=1;i<h+1;i++){
            getchar();
            //string str="";
            //getline(cin,str);
            for(int j=1;j<w+1;j++){
                //s[i][j]=str[j-1];
                s[i][j]=getchar();
            }
        }
        for (int i = 0; i <= w; i ++)
            s[h + 1][i + 1] = ' ';
        for (int i = 0; i <= h; i ++)
            s[i + 1][w + 1] = ' ';
        cout<<"Board #"<<id<<":"<<endl;
        id++;
        int x1,y1,x2,y2;
        int subId=0;
        while(1){
            subId++;
             totalStep=100000;
             memset(mark, 100000, sizeof(mark));
            cin>>x1>>y1>>x2>>y2;
            ques.push(new Node(x1,y1));
            mark[y1][x1]=1;
            if(x1==0&&y1==0&&x2==0&&y2==0) break;
            int step=0;
            int direct=-1;
            findTotalPath(x1,y1,x2,y2,direct,step);
            if(totalStep<100000)
                cout<<"Pair "<<subId<<": "<<totalStep<<" segments."<<endl;
            else{
                cout<<"Pair "<<subId<<": "<<"impossible."<<endl;
            }
            for(int i=0;i<h+2;i++){
                for(int j=0;j<w+2;j++){
                    directStep[i][j]=new directNode(-1,0);
                }
        }
        }
        while(ques.size()>0){
            ques.pop();
        }
        cout<<endl;
    }
}