A great problem that requires building a graph in a non-obvious way. Problem link

At first glance, it's not obvious to build a graph, but with some thought it's not too hard.

The idea is to set edge weights to 0 for moving onto lily pads and 1 for moving on to water cells. Then just run Dijkstra. That should be straightforward, and indeed it took only 20 minutes to code.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 45 * 45;
const int MAXM = 10000000;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, val, nxt;
} e[MAXM];

struct Node {
    int to, val;
    bool operator < (const Node &other) const {
        return val > other.val;
    }
};

priority_queue<Node> pq;
bool vis[MAXN];
int head[MAXN], cnt, n, m, _mp[50][50], start, dest, dis[MAXN], ways[MAXN];
const int dx[] = {1,1,-1,-1,2,2,-2,-2};
const int dy[] = {2,-2,2,-2,1,-1,1,-1};

inline int id(int x, int y) { return (x-1)*m + y; }

void addEdge(int u, int v, int w) {
    e[++cnt] = {v, w, head[u]};
    head[u] = cnt;
}

void build(int x, int y) {
    if (_mp[x][y] == 3) start = id(x,y);
    if (_mp[x][y] == 4) dest = id(x,y);
    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
        if (_mp[nx][ny] == 2) continue;
        if (_mp[nx][ny] == 1 || _mp[nx][ny] == 4) addEdge(id(x,y), id(nx,ny), 0);
        if (_mp[nx][ny] == 0) addEdge(id(x,y), id(nx,ny), 1);
    }
}

void init() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> _mp[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            build(i, j);
}

void dijkstra() {
    init();
    memset(dis, 0x3f, sizeof(dis));
    memset(ways, 0, sizeof(ways));
    dis[start] = 0; ways[start] = 1;
    pq.push({start, 0});
    while (!pq.empty()) {
        int u = pq.top().to; pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (vis[v]) continue;
            if (dis[v] > dis[u] + e[i].val) {
                dis[v] = dis[u] + e[i].val;
                ways[v] = ways[u];
                pq.push({v, dis[v]});
            } else if (dis[v] == dis[u] + e[i].val) {
                ways[v] += ways[u];
            }
        }
    }
    if (ways[dest] == 0) cout << -1 << endl;
    else cout << dis[dest] << endl << ways[dest] << endl;
}

int main() {
    dijkstra();
    return 0;
}

This code only gets 50 points. After checking, the issue is that the problem asks for the number of ways to place lily pads, not the number of shortets paths. So we need a different approach.

How to solve? Use DFS to build edges only from water or start cells. If we encounter a lily pad, treat it as part of the water cell it originated from, so we build edges from the oriignal water cell through the lily pad to other cells. Plus some extra details.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 51 * 51;
const int MAXM = 10000000;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, val, nxt;
} e[MAXM];

struct Node {
    int to, val;
    bool operator < (const Node &other) const {
        return val > other.val;
    }
};

priority_queue<Node> pq;
bool vis[MAXN], visited[MAXN][MAXN];
int head[MAXN], cnt, n, m, _mp[50][50], start, dest, dis[MAXN];
ll ways[MAXN];
const int dx[] = {1,1,-1,-1,2,2,-2,-2};
const int dy[] = {2,-2,2,-2,1,-1,1,-1};

inline int id(int x, int y) { return (x-1)*m + y; }

void addEdge(int u, int v, int w) {
    e[++cnt] = {v, w, head[u]};
    head[u] = cnt;
}

void dfs(int x, int y, int orig) {
    visited[x][y] = 1;
    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
        if (visited[nx][ny] || _mp[nx][ny] == 2) continue;
        if (_mp[nx][ny] == 1) dfs(nx, ny, orig);
        else {
            visited[nx][ny] = 1;
            addEdge(orig, id(nx, ny), 1);
        }
    }
}

void build(int x, int y) {
    if (_mp[x][y] == 3) start = id(x,y);
    if (_mp[x][y] == 4) dest = id(x,y);
    if (_mp[x][y] == 0 || _mp[x][y] == 3 || _mp[x][y] == 4) {
        memset(visited, 0, sizeof(visited));
        dfs(x, y, id(x,y));
    }
}

void init() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> _mp[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            build(i, j);
}

void dijkstra() {
    init();
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(ways, 0, sizeof(ways));
    dis[start] = 0; ways[start] = 1;
    pq.push({start, 0});
    while (!pq.empty()) {
        int u = pq.top().to; pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (vis[v]) continue;
            if (dis[v] > dis[u] + e[i].val) {
                dis[v] = dis[u] + e[i].val;
                ways[v] = ways[u];
                pq.push({v, dis[v]});
            } else if (dis[v] == dis[u] + e[i].val) {
                ways[v] += ways[u];
            }
        }
    }
    if (ways[dest] == 0) cout << -1 << endl;
    else cout << dis[dest] - 1 << endl << ways[dest] << endl;
}

int main() {
    dijkstra();
    return 0;
}