首页 > 代码库 > 【bfs】【中等难度】wikioi3055 青铜莲花池
【bfs】【中等难度】wikioi3055 青铜莲花池
3055 青铜莲花池
题目描述 Description
为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了M 行N 列个方格（1 ≤ M, N ≤ 30）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲 花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。
贝西的舞步很像象棋中的马步：每次总是先横向移动M1 (1 ≤ M1 ≤ 30)格，再纵向移动M2 (1 ≤ M2 ≤ 30, M1≠M2)格，或先纵向移动M1 格，再横向移动M2 格。最多时，贝西会有八个移动方向可供选择。给定池塘的布局和贝西的跳跃长度，请计算贝西从起点出发，到达目的地的最小步数，我们保证输入数据中的目的地一定是可达的。
输入描述 Input Description
第一行：四个用空格分开的整数：M，N，M1 和M2
第二行到M + 1 行：第i + 1 行有N 个用空格分开的整数，描述了池塘第i 行的状态：0 为水，1 为莲花，2 为岩石，3 为贝西所在的起点，4 为贝西想去的终点。
输出描述 Output Description
第一行：从起点到终点的最少步数。
样例输入 Sample Input
4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
【样例说明】
贝西从第二行的最左边出发，目标是第二行的最右边。
贝西先跳到第一行第三列的莲花上，再跳到终点，需要两步。之所以叫青铜莲花池，是因为这是青铜组的，而我们还有白银组、黄金组！
思路Thinkings
这道题就是最基本的bfs啦。STL的队列我似乎不会用，不过手写一个应该不是太难的问题吧。。卡了那么久。。还是上次那个原因：cin>>M>>N;判断边界是否溢出的条件是:if ( (x>0) && (x<=M) && (y>0) && (y<=N) && (没有走过) &&(路通) ) { …… }具体……的内容等会儿弄个框架。。。p.s.：你不是说有黄金组的吗，白银组的吗？在哪儿在哪儿？
代码code
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 using namespace std; 5 struct note 6 { 7 int x,y,step; 8 }; 9 int N,M,M1,M2;10 int xx[10];11 int yy[10]; 12 int board[50][50];13 int gone[50][50]={0};14 note queue[10005];15 int startx,starty,ansx,ansy,qh,qt;16 note now,next;17 void readin()18 {19 cin>>M>>N>>M1>>M2;20 for (int i=1;i<=M;i++)21 { 22 for (int j=1;j<=N;j++) 23 {24 cin>>board[i][j];25 gone[i][j]=0;26 if (board[i][j]==3) {startx=i;starty=j;board[i][j]=1;gone[i][j]=1;} 27 if (board[i][j]==4) {ansx=i;ansy=j;board[i][j]=1;gone[i][j]=0;}28 }29 } 30 xx[1]=M1; xx[2]=M2; xx[3]=M2; xx[4]=M1; xx[5]=-M1; xx[6]=-M2; xx[7]=-M2; xx[8]=-M1; 31 yy[1]=M2; yy[2]=M1; yy[3]=-M1; yy[4]=-M2; yy[5]=-M2; yy[6]=-M1; yy[7]=M1; yy[8]=M2;32 now.x=startx;now.y=starty; now.step=0;33 queue[1]=now;34 qh=1;qt=1;;35 }36 37 int main()38 {39 readin();40 while ( qh<=qt )41 {42 now=queue[qh];43 qh++;44 if ( (now.x==ansx) && (now.y==ansy) ) { cout<<now.step<<endl; return 0; }45 next.step=now.step+1;46 for (int i=1;i<=8;i++)47 {48 next.x=now.x+xx[i];49 next.y=now.y+yy[i];50 if ( (next.x==ansx) && (next.y==ansy) ) { cout<<next.step<<endl; return 0; }51 if ( (next.x>0) && (next.x<=M) && (next.y>0) && (next.y<=N) && (board[next.x][next.y]==1) && (gone[next.x][next.y]==0))52 {53 gone[next.x][next.y]=1;54 qt++;55 queue[qt]=next;56 }57 } 58 }59 60 return 0; 61 }
结果
p.s.：哎，还是有耗时，毕竟我很笨……
框架
恩，给自己弄个框架吧。。毕竟搜索是世界上最难的算法——暴力的一种嘛
struct note{ int x,y,step;};note queue[];int main(){ cin>>M>>N; 各种读入; queue[1].x=startx;queue[1].y=starty;queue[1].step=0; head=1;tail=1; while (head<=tail) { if (符合答案) {cout<<queue[head].step;return 0;} for (i=1;i<=情况数;i++) { x=queue[head].x+movex[i]; y=queue[head].x+movey[i]; if ( (x>0) && (x<=M) && (y>0) && (y<=N) && (没有走过) &&(路通) ) { tail+=1; queue[tail].x=x;queue[tail].y=y;queue[tail].step=queue[head].step+1; } } head+=1; }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。