题目描述

Farmer John为了满足奶牛对美的享受而安装了人工湖。矩形的人工湖分成行列的方形小格子。有些格子有美丽的荷叶，有些有岩石，剩下的格子有的只是美丽的蓝色湖水。
Bessie通过从一片荷叶跳到另一片荷叶上来练习芭蕾。它现在正站在一片荷叶上（看输入数据了解具***置）。它希望通过在荷叶上跳跃来到达另一片荷叶。它既不能跳到水里也不能跳到岩石上。
只有新手才会感到吃惊：Bessie的跳跃有点类似国际象棋中马那样的移动，在一个方向上移动“格”，然后再在斜方向上移动格（或者也许在一个方向上移动格，然后在斜方向上移动格）。Bessie有时可能有多达8中的跳跃选择。
给出池塘的构造以及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;
}

来源：YDDDD