洛谷P2411 [USACO07FEB] Silver Lilypad Pond S 题解

题目链接：P2411 [USACO07FEB] Silver Lilypad Pond S

题意：

为了让奶牛们娱乐和锻炼，Famer John 建造了一个美丽的池塘。这个长方形的池子被分成了 $M \times N$ 个方格（$1 \le M,N \le 30$）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。

Bessie 正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。

Bessie 的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，Bessie 会有八个移动方向可供选择。

约翰一直在观看 Bessie 的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。

于是他想要添加几朵莲花来帮助 Bessie 完成任务。一贯节俭的 John 只想添加最少数量的莲花，当然，莲花不能放在石头上。

请帮助 John确定必须要添加的莲花的最少数量。在添加莲花最少的基础上，确定 Bessie 从起点跳到目标需要的最少步数。最后，确定满足添加的莲花数量最少时，步数最少的路径条数。

输入格式：

第一行，输入两个用空格分开的整数：$M$ 和 $N$。

第二行到 $M + 1$ 行：第 $i + 1$ 行有 $N$ 个用空格分开的整数，描述了池塘第 $i$ 行的状态：0 为水，1 为莲花，2 为岩石，3 为 Bessie 所在的起点，4 为 Bessie 想去的终点。

输出格式：

第一行，一个整数，表示需要添加的莲花的最少数目；如果无解，则输出 $-1$。

第二行，一个整数，表示在添加莲花最少的基础上，贝西从起点跳到终点需要的最少步数；如果第一行是 $-1$，不输出这行。

第三行，一个整数，表示在添加莲花最少的基础上，步数等于第二行输出的路径条数；如果第一行是 $-1$，不输出这行。

搞了半天，这题不就是个路径计数问题么。

不要被它的两种权值迷惑了，最少步数只可能在添加数目相等时才能更新。

这里因为一开始想的是 BFS ，所以写的是 SPFA ，反正 $n,m$ 小的可怜也无所谓。

时间复杂度 $\mathcal{O}(nm)$ ，甚至跑到了最优解

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(35))

int a[N][N], d[N][N], f[N][N], c[N][N];
char vis[N][N];
int sx, sy, ex, ey; queue<pii> q;
const int dx[] = {1, 1, 2, 2, -1, -1, -2, -2};
const int dy[] = {2, -2, 1, -1, 2, -2, 1, -1};
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j]; c[i][j] = d[i][j] = INF;
            if(a[i][j] == 3) {
                tie(sx, sy) = tie(i, j); c[i][j] = d[i][j] = 0;
                f[i][j] = 1; vis[i][j] = true; q.push({i, j});
            }
            if(a[i][j] == 4) tie(ex, ey) = tie(i, j);
        }
    while(!q.empty())
    {
        auto [x, y] = q.front(); q.pop(); vis[x][y] = false;
        for(int i = 0; i < 8; i++)
        {
            int tx = x + dx[i], ty = y + dy[i];
            if(tx > 0 && tx <= n && ty > 0 && ty <= m && a[tx][ty] != 2)
            {
                int cost = c[x][y] + (a[tx][ty] == 0);
                if(cost < c[tx][ty]) {
                    c[tx][ty] = cost; d[tx][ty] = d[x][y] + 1; f[tx][ty] = f[x][y];
                    if(!vis[tx][ty]) { vis[tx][ty] = true; q.push({tx, ty}); }
                }else if(cost == c[tx][ty])
                {
                    if(d[x][y] + 1 < d[tx][ty]) {
                        d[tx][ty] = d[x][y] + 1; f[tx][ty] = f[x][y];
                    }else if(d[x][y] + 1 == d[tx][ty]) {
                        f[tx][ty] += f[x][y];
                    }
                }
            }
        }
    }
    if(c[ex][ey] == INF) return cout << "-1\n", 0;
    cout << c[ex][ey] << '\n' << d[ex][ey] << '\n' << f[ex][ey] << '\n';
    return 0;
}