题意分析

Jill 需要在网格地图中寻找从起点到终点的最短路径，需满足以下条件：

海拔限制：相邻网格的海拔差不能超过 10 米（目标网格海拔需 ≤ 当前网格海拔 + 10）。 单向道路限制：只能沿地图中标记的单向道路方向移动。 最短路径优先：在满足条件的路径中选择最短路径（网格步数最少）。

解题思路

利用 BFS 逐层探索所有可达网格，确保首次到达终点的路径为最短路径（BFS 特性）。

#include <iostream>
using namespace std;

const int ds[4] = { -1,0,0,1 };
const int da[4] = { 0,1,-1,0 };
struct State
{
    int s, a; //(s,a)为网格的行列坐标
};
int n, m;
int alt[20][20];  //海拔高度
int s1, a1, s2, a2;//当前单项路起点和终点的坐标
int ss, as, se, ae;  //jill起点和终点的坐标
int isd[20][20][4];//是否有通向d方向的路
int par[20][20];//标记到达网格点的方向
State qu[400];//duilie
int qs, qt;

void Bfs();
void Print(int ss, int as, int se, int ae);
int Getdirection(); //求得当前单向路线的方向索引

int main()
{
    int d, i, j;
    while (cin >> n >> m)
    {
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < m; j++)
            {
                cin >> alt[i][j];
                isd[i][j][0] = isd[i][j][1] = isd[i][j][2] = isd[i][j][3] = 0;
            }
        }
        while (cin >> s1 >> a1 >> s2 >> a2)
        {
            if (s1 == 0 && s2 == 0 && a1 == 0 && a2 == 0) break;
            s1--; a1--; s2--; a2--;
            d = Getdirection();
            while (s1 != s2 || a1 != a2)
            {
                isd[s1][a1][d] = 1;
                s1 += ds[d]; a1 += da[d];
            }
        }
        while (cin >> ss >> as >> se >> ae)
        {
            if (ss == 0 && as == 0 && se == 0 && ae == 0)
                break;
            ss--; as--; se--; ae--;
            if (ss == se && as == ae)
            {
                cout << "To get from " << ss + 1 << "-" << as + 1 << " to " << se + 1
                    << "-" << ae + 1 << ", stay put! ";
            }
            else
            {
                for (i = 0; i < n; i++)
                {
                    for (j = 0; j < m; j++)
                        par[i][j] = -1;
                }
                Bfs();
                if (par[se][ae] == -1)
                    cout << "There is no acceptable route from " << ss + 1 << "-"
                    << as + 1 << " to " << se + 1 << "-" << ae + 1 << ".";
                else
                    Print(ss, as, se, ae);
            }
            cout << "\n\n";
        }
    }
    return 0;
}
void Bfs()
{
    int i;
    qu[0].s = ss; qu[0].a = as;
    qs = 0; qt = 1;
    while (qs < qt)
    {
        for (i = 0; i < 4; i++)
        {
            int cs = qu[qs].s + ds[i];
            int ca = qu[qs].a + da[i];
            if (cs < 0 || cs >= n || ca < 0 || ca >= m) continue;
            if (par[cs][ca] != -1 || isd[qu[qs].s][qu[qs].a][i] == 0
                || alt[cs][ca] - alt[qu[qs].s][qu[qs].a] > 10) continue;
            par[cs][ca] = i;
            qu[qt].s = cs; qu[qt].a = ca; qt++;
        }
        qs++;
    }
}
void Print(int ss, int as, int se, int ae)
{
    if (ss != se || as != ae)
    {
        int cd = par[se][ae];
        Print(ss, as, se - ds[cd], ae - da[cd]);
        cout << " to ";
    }
    cout << se + 1 << "-" << ae + 1;
}
int Getdirection()
{
    if (s1 == s2)
    {
        if (a1 < a2) return 1;
        else return 2;
    }
    else
    {
        if (s1 < s2) return 3;
        else return 0;
    }
}