题解 | 跳跃-牛客假日团队赛2F题
F-跳跃_牛客假日团队赛2
https://ac.nowcoder.com/acm/contest/924/F
题目描述
Farmer John为了满足奶牛对美的享受而安装了人工湖。矩形的人工湖分成
行
列)
的方形小格子。有些格子有美丽的荷叶，有些有岩石，剩下的格子有的只是美丽的蓝色湖水。
Bessie通过从一片荷叶跳到另一片荷叶上来练习芭蕾。它现在正站在一片荷叶上（看输入数据了解具***置）。它希望通过在荷叶上跳跃来到达另一片荷叶。它既不能跳到水里也不能跳到岩石上。
只有新手才会感到吃惊：Bessie的跳跃有点类似国际象棋中马那样的移动，在一个方向上移动)
“格”，然后再在斜方向上移动)
格（或者也许在一个方向上移动
格，然后在斜方向上移动
格）。Bessie有时可能有多达8中的跳跃选择。
给出池塘的构造以及Bessie跳跃的形式，找出Bessie从一个位置移动到另一个位置所需的最小的跳跃次数。这个跳跃对于所给的测试数据总是可能的。
Bessie通过从一片荷叶跳到另一片荷叶上来练习芭蕾。它现在正站在一片荷叶上（看输入数据了解具***置）。它希望通过在荷叶上跳跃来到达另一片荷叶。它既不能跳到水里也不能跳到岩石上。
只有新手才会感到吃惊：Bessie的跳跃有点类似国际象棋中马那样的移动，在一个方向上移动
给出池塘的构造以及Bessie跳跃的形式，找出Bessie从一个位置移动到另一个位置所需的最小的跳跃次数。这个跳跃对于所给的测试数据总是可能的。
输入描述:
第 1 行: 四个空格分开的整数：和
第 2 至行: 第
行用
行，0表示水，1表示 荷叶，2表示岩石，3表示Bessie现在站的那块荷叶，4表示跳跃的 终点。
输出描述:
第 1 行: 一个整数，是Bessie从一块荷叶跳到另一块荷叶所需的最小的跳跃数。
示例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
输出
2
说明
Bessie在第二行的左边开始；她的目的地在第二行的右边。池塘中有几块荷叶和岩石。
Bessie聪明的跳到了(1,3)的荷叶上，再跳到目的地。
解答
BFS模板，唯一注意的就是下一步的位置。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 50 + 10;
const int MOD = 1e9 + 7;
struct Node
{
int x_, y_;
int step_;
Node(int x, int y, int step):x_(x), y_(y), step_(step){}
};
int n, m, k, t;
int m1, m2, s, e;
int Map[MAXN][MAXN];
int Bfs(int Next[8][2])
{
queue<Node> que;
que.emplace(s, e, 0);
while (!que.empty())
{
Node now = que.front();
que.pop();
for (int i = 0;i < 8;i++)
{
int nx = now.x_+Next[i][0];
int ny = now.y_+Next[i][1];
if (nx < 1 || nx > n || ny < 1 || ny > m)
continue;
if (Map[nx][ny] == 4)
return now.step_+1;
if (Map[nx][ny] != 1)
continue;
que.emplace(nx, ny, now.step_+1);
Map[nx][ny] = 0;
}
}
return 0;
}
int main()
{
cin >> n >> m >> m1 >> m2;
for (int i = 1;i <= n;i++)
{
for (int j = 1; j <= m; j++)
{
cin >> Map[i][j];
if (Map[i][j] == 3)
s = i, e = j;
}
}
int Next[8][2] = {{-m1, -m2}, {-m1, m2}, {-m2, -m1}, {-m2, m1},
{m1, -m2}, {m1, m2}, {m2, -m1}, {m2, m1}};
int res = Bfs(Next);
cout << res << endl;
return 0;
} 
