首页 > 代码库 > 青铜莲花池(Bronze Lilypad Pond, USACO 2007 Feb)
青铜莲花池(Bronze Lilypad Pond, USACO 2007 Feb)
题目描述
为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 M 行 N 列个方格(1 ≤ M, N ≤ 30) 。一些格子是坚固得令人惊讶的莲花,还有一些格子是岩石,其余的只是美丽、纯净、湛蓝的水。
贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。
贝西的舞步很像象棋中的马步:每次总是先横向移动 M1 (1 ≤ M1 ≤ 30)格,再纵向移动 M2 (1 ≤ M2 ≤ 30, M1≠M2)格,或先纵向移动 M1 格,再横向移动 M2 格。最多时,贝西会有八个移动方向可供选择。
给定池塘的布局和贝西的跳跃长度,请计算贝西从起点出发,到达目的地的最小步数,我们保证输入数据中的目的地一定是可达的。
输入输出格式
输入格式:
第一行:四个用空格分开的整数:M,N,M1 和 M2
第二行到 M + 1 行:第 i + 1 行有 N 个用空格分开的整数,描述了池塘第
i 行的状态:0 为水,1 为莲花,2 为岩石,3 为贝西所在的起点,4 为贝西想去
的终点。
输出格式:
第一行:从起点到终点的最少步数。
输入输出样例
输入样例#1:
4 5 1 2 1 0 1 0 1 3 0 2 0 4 0 1 2 0 0 0 0 0 1 0
输出样例#1:
2
由于题目数据很小,所以直接用bfs搜索即可
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<algorithm> using namespace std; struct pos { int x,y; int step; }; int m1,m2,m,n,ans=0; int maps[35][35]; bool vis[35][35]; pos s,t; void bfs(pos s) { int dx[10]={m1,m1,m2,m2,-m1,-m1,-m2,-m2}; int dy[10]={m2,-m2,m1,-m1,m2,-m2,m1,-m1}; queue<pos>q; s.step=0; vis[s.x][s.y]=1; q.push(s); while(!q.empty()) { pos now=q.front(); q.pop(); if(now.x==t.x && now.y==t.y) { ans=now.step; return; } for(int i=0;i<8;i++) { pos v; v.x=now.x+dx[i]; v.y=now.y+dy[i]; if(v.x>=1 && v.x<=m && v.y>=1 && v.y<=n && !vis[v.x][v.y] && (maps[v.x][v.y]==1 || maps[v.x][v.y]==4)) { vis[v.x][v.y]=1; v.step=now.step+1; q.push(v); } } } } int main() { scanf("%d%d%d%d",&m,&n,&m1,&m2); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { scanf("%d",&maps[i][j]); if(maps[i][j]==3) s.x=i,s.y=j; if(maps[i][j]==4) t.x=i,t.y=j; } bfs(s); printf("%d",ans); }
青铜莲花池(Bronze Lilypad Pond, USACO 2007 Feb)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。