首页 > 代码库 > 青铜莲花池
青铜莲花池
Farmer John为了满足宁智贤对美的享受而安装了人工湖。矩形的人工湖分成
M行N列(1 <= M <= 30; 1 <= N <= 30)的方形小格子。有些格子有美丽的荷
叶，有些有岩石，剩下的格子有的只是美丽的蓝色湖水。
宁智贤通过从一片荷叶跳到另一片荷叶上来练习芭蕾。它现在正站在一片荷叶
上（看输入数据了解具体位置）。它希望通过在荷叶上跳跃来到达另一片荷叶。
它既不能跳到水里也不能跳到岩石上。
只有新手才会感到吃惊：宁智贤的跳跃有点类似国际象棋中马那样的移动，在一
个方向上（如水平方向）移动M1(1 <= M1 <= 30)“格”，然后再在另一个方向上（如竖直方向）移动M2 (1 <= M2 <= 30; M1 != M2)格，所以宁智贤有时可能有多达8中的跳跃选择。
给出池塘的构造以及宁智贤跳跃的形式，找出宁智贤从一个位置移动到另一个位置
所需的最小的跳跃次数。这个跳跃对于所给的测试数据总是可能的。
INPUT:（m,n,m1,n1\\+m*n的map）
4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0
输入说明:
宁智贤在第二行的左边开始；她的目的地在第二行的右边。池塘中有几块荷叶和岩石。
OUTPUT：（步数）
2
输出说明:
机智的宁智贤跳到了(1,3)的荷叶上，再跳到目的地。
题解：
在输入是可以很方便的找出stx,sty和enx,eny;然后就是找可以跳的地方。用dx【8】，dy【8】把宁志贤可以跳的方向列举出来；
然后用BFS来找出他可以跳的路径。但是又有一个问题，他所跳的路径不一定是最小的，所以就需要一个记录现在位置的结构体。
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdio> 6 #include<cstdlib> 7 #include<algorithm> 8 #include<queue> 9 using namespace std;10 const int maxn =33; 11 int map[maxn][maxn]; 12 struct node{ 13 int x,y; 14 int step; 15 }s_pos; 16 int m,n,m1,m2,step; 17 int sx,sy,ex,ey; 18 bool vis[maxn][maxn]; 19 bool check(int x,int y){ 20 return x>=0&&x<m&&y>=0&&y<n; 21 } 22 void bfs(){ 23 int dx[8]={-m1,-m1,m1,m1,-m2,-m2,m2,m2}; 24 int dy[8]={m2,-m2,m2,-m2,m1,-m1,m1,-m1}; 25 queue<node> q; 26 s_pos.x=sx; s_pos.y=sy; s_pos.step=0; 27 q.push(s_pos); 28 vis[sx][sy]=true; 29 while(!q.empty()){ 30 node now = q.front();q.pop(); 31 if(now.x==ex&&now.y==ey){ 32 step=now.step;return; 33 } 34 for(int i=0;i<8;i++){ 35 int nx=now.x+dx[i]; int ny=now.y+dy[i]; 36 if(check(nx,ny)&&!vis[nx][ny]&&(map[nx][ny]==1||map[nx][ny]==4)){ 37 node next = now; 38 next.x=nx; next.y=ny; next.step++; 39 q.push(next);40 vis[nx][ny]=true; 41 } 42 43 } 44 45 } 46 } 47 int main(){ 48 scanf("%d%d%d%d",&m,&n,&m1,&m2); 49 for(int i=0;i<m;i++) for(int j=0;j<n;j++) scanf("%d",&map[i][j]); 50 for(int i=0;i<m;i++){ 51 for(int j=0;j<n;j++){ 52 if(map[i][j]==3){ 53 sx=i;sy=j; 54 } 55 if(map[i][j]==4){ 56 ex=i;ey=j; 57 } 58 } 59 } 60 bfs(); 61 printf("%d\n",step); 62 return 0; 63 }
青铜莲花池
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。