简答

地图是方格，贝西走马步（和象棋马一样 8 个方向跳），只能踩莲花才能落脚。岩石永远不能走。
有些格子不是莲花，可以花钱改造：普通水面改造花 1 点体力；铂金格子要花 2 点体力，改完还能拿到铂金；本来就是莲花的不用花钱。
我们要找从起点跳到终点的路线，优先目标：整条路线改造花费的体力尽量少，而且总花费不能超过约翰手里的体力上限。
在花费达到最少的前提下，再看第二个目标：这条最少花费的路线里面，能拿到的铂金数量要尽可能多。
同时还要计数：
有多少条路线，刚好是这个最小体力消耗；
在最小体力、并且铂金拿到最多的条件下，又有多少条这样的路线。
因为不同格子改造花的体力不一样，不能用简单广度搜索，要用 Dijkstra 这类优先队列的搜索，每次优先处理消耗更低的路线。
搜的时候每个格子记住四件事：到这里最少要多少体力、有几条这样的路；在这个最少体力下最多拿多少铂金、对应有几条路。
全部搜完之后看终点：
如果最少消耗超过约翰的体力，直接输出 - 1；
否则输出最小消耗和对应路线总数；
再看在这个最小消耗下能不能拿到铂金，能就输出最多铂金数量和对应的路线数，拿不到就输出 - 1。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pid(x, y) ((x - 1) * n + (y - 1))
int m, n, p;
struct Edge {
int to, next, w;
} e[200005];
int head[905], len;
void Insert(int u, int v, int w) {
e[len].to = v;
e[len].next = head[u];
e[len].w = w;
head[u] = len;
}
int mp[905];
int sx, sy, tx, ty;
int d[905], pt[905];
ll f[905], g[905];
bool vis[905], mkd[905];
struct ND {
int num, dis;
bool operator<(const ND &o) const {
return dis > o.dis;
}
};
void dfs(int x, int y, int rx, int ry) {
vis[pid(x, y)] = true;
int dx[] = {2, 2, -2, -2, 1, 1, -1, -1};
int dy[] = {1, -1, 1, -1, 2, -2, 2, -2};
for (int i = 0; i < 8; i) {
if (x + dx[i] < 1 || x + dx[i] > m || y + dy[i] < 1 || y + dy[i] > n) continue;
if (mp[pid(x + dx[i], y + dy[i])] == 0) {
if (!mkd[pid(x + dx[i], y + dy[i])]) Insert(pid(rx, ry), pid(x + dx[i], y + dy[i]), 1);
mkd[pid(x + dx[i], y + dy[i])] = true;
}
else if (mp[pid(x + dx[i], y + dy[i])] == 4) {
if (!mkd[pid(x + dx[i], y + dy[i])]) Insert(pid(rx, ry), pid(x + dx[i], y + dy[i]), 0);
mkd[pid(x + dx[i], y + dy[i])] = true;
}
else if (mp[pid(x + dx[i], y + dy[i])] == 5) {
if (!mkd[pid(x + dx[i], y + dy[i])]) Insert(pid(rx, ry), pid(x + dx[i], y + dy[i]), 2);
mkd[pid(x + dx[i], y + dy[i])] = true;
}
else if (mp[pid(x + dx[i], y + dy[i])] == 1) {
if (!vis[pid(x + dx[i], y + dy[i])]) dfs(x + dx[i], y + dy[i], rx, ry);
}
}
}
void Dijkstra() {
priority_queue<ND> q;
q.push({pid(sx, sy), 0});
memset(d, 0x3f, sizeof(d));
d[pid(sx, sy)] = 0;
f[pid(sx, sy)] = 1;
g[pid(sx, sy)] = 1;
while (!q.empty()) {
int u = q.top().num; q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (d[v] == d[u] + e[i].w) {
f[v] += f[u];
if (pt[v] == pt[u] + (e[i].w == 2)) {
g[v] += g[u];
}
else if (pt[v] < pt[u] + (e[i].w == 2)) {
pt[v] = pt[u] + (e[i].w == 2);
g[v] = g[u];
}
}
else if (d[v] > d[u] + e[i].w) {
d[v] = d[u] + e[i].w;
f[v] = f[u];
g[v] = g[u];
pt[v] = pt[u] + (e[i].w == 2);
q.push({v, d[v]});
}
}
}
}
int main() {
scanf("%d%d%d", &p, &m, &n);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &mp[pid(i, j)]);
if (mp[pid(i, j)] == 3) {
sx = i; sy = j;
mp[pid(i, j)] = 0;
}
else if (mp[pid(i, j)] == 4) {
tx = i; ty = j;
}
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
memset(vis, 0, sizeof(vis));
memset(mkd, 0, sizeof(mkd));
if (mp[pid(i, j)] == 0 || mp[pid(i, j)] == 5) dfs(i, j, i, j);
}
}
Dijkstra();
if (d[pid(tx, ty)] > p) {
puts("-1");
return 0;
}
printf("%d %lld\n", d[pid(tx, ty)], f[pid(tx, ty)]);
if (!pt[pid(tx, ty)]) {
puts("-1");
return 0;
}
printf("%d %lld\n", pt[pid(tx, ty)], g[pid(tx, ty)]);
return 0;
}

所以总的来说，题目并不简单。