AOJ 865.青铜莲花池

149


题目



点击显/隐题目

为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了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 为贝西想去的终点。


第一行:从起点到终点的最少步数


4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0 4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0


22




题解


标准的BFS问题,节点的拓展方式比较多
题意为每一步是先跳到一个荷叶,再跳到另一片荷叶
实际操作不考虑中间的荷叶是否能走


代码


点击显/隐代码
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 35;
const int delta[4][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
int Map[maxn][maxn];

struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
bool operator==(const Point &rhs) const { return x == rhs.x && y == rhs.y; }
};

queue<Point> Q;
int dis[maxn][maxn];
int bfs(int m, int n, int d1, int d2, Point s, Point v) {
memset(dis, 0, sizeof(dis));
while (!Q.empty())
Q.pop();

Q.push(s);
dis[s.x][s.y] = 0;

while (!Q.empty()) {
Point t = Q.front();
Q.pop();
if (t == v)
break;

for (int i = 0; i < 4; i++) {
int xx = t.x + delta[i][0] * d1;
int yy = t.y + delta[i][1] * d2;

if (xx < 0 || xx >= m || yy < 0 || yy >= n)
continue;
if (dis[xx][yy] || Map[xx][yy] == 0 || Map[xx][yy] == 2)
continue;
// if (!(Map[t.x][yy] == 1 || Map[xx][t.y] == 1 || Map[t.x][yy] == 4 || Map[xx][t.y] == 4))
// continue;

dis[xx][yy] = dis[t.x][t.y] + 1;
Q.push(Point(xx, yy));
}
for (int i = 0; i <= 3; i++) {
int xx = t.x + delta[i][0] * d2;
int yy = t.y + delta[i][1] * d1;

if (xx < 0 || xx >= m || yy < 0 || yy >= n)
continue;
if (dis[xx][yy] || Map[xx][yy] == 0 || Map[xx][yy] == 2)
continue;
// if (!(Map[t.x][yy] == 1 || Map[xx][t.y] == 1 || Map[t.x][yy] == 4 || Map[xx][t.y] == 4))
// continue;

dis[xx][yy] = dis[t.x][t.y] + 1;
Q.push(Point(xx, yy));
}
}
return dis[v.x][v.y];
}

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif

cin.tie(0);
cin.sync_with_stdio(false);
int M, N, M1, M2;
Point s, v;
while (scanf("%d%d%d%d", &M, &N, &M1, &M2) != EOF) {
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++) {
scanf("%d", &Map[i][j]);
if (Map[i][j] == 3) {
s.x = i;
s.y = j;
}
if (Map[i][j] == 4) {
v.x = i;
v.y = j;
}
}
}
printf("%d\n", bfs(M, N, M1, M2, s, v));
// for (int i = 0; i < M; i++) {
// for (int j = 0; j < N; j++)
// printf("%d ", dis[i][j]);
// printf("\n");
// }
#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论