2802:小游戏利用bfs来实现
2018-06-17 20:25:47来源:未知 阅读 ()
之前使用的是递归的方法来解决的问题,后来有点想用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; } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:设计模式—桥接模式的C++实现
下一篇:线性筛素数详细整理
- 图的连通分量(利用邻接表存储信息) 2020-04-02
- 小游戏二之---------------五子棋 2020-03-23
- 利用kindlegen实现txt格式小说转换为mobi格式小说(C++实现 2020-01-30
- 结题报告 2020-01-12
- 顺序栈的表示与实现 2019-10-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash