感觉应当挺简单的,但是弄了好久……菜死了
如果不考虑那些为$1$的点,直接跑个最短路计数就好了,但是我们现在有一些边可以不用付出代价,那么只要在连边的时候先预处理搜一下就好了。
原来的想法是拆点,但是这样子不好连边,所以直接把点权转化到边权上来。
注意到起点其实不用付出代价,那么最后的答案就是$dis_ed - 1$。
时间复杂度上界是$O(n^4 + n^2log(n^2))$。
Code:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <cstdio> #include <cstring> #include <queue> using namespace std; typedef long long ll; typedef pair <ll, int> pin; const int N = 1005; const int M = 2e5 + 5; const int L = 35; const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}; const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2}; const ll inf = 0x3f3f3f3f3f3f3f3f; int n, m, a[L][L], tot = 0, head[N]; ll dis[N], cnt[N]; bool vis[N], ins[L][L]; struct Edge { int to, nxt; } e[M]; inline void add(int from, int to) { e[++tot].to = to; e[tot].nxt = head[from]; head[from] = tot; } template <typename T> inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } inline int id(int x, int y) { return (x - 1) * m + y; } void dfs(int nowId, int x, int y) { ins[x][y] = 1; for(int i = 0; i < 8; i++) { int tox = x + dx[i], toy = y + dy[i]; if(tox < 1 || tox > n || toy < 1 || toy > m) continue; if(ins[tox][toy]) continue; if(a[tox][toy] == 1) dfs(nowId, tox, toy); else ins[tox][toy] = 1, add(nowId, id(tox, toy)); } } priority_queue <pin> Q; void dij(int st) { memset(dis, 0x3f, sizeof(dis)); cnt[st] = 1LL, dis[st] = 0LL; Q.push(pin(0, st)); for(; !Q.empty(); ) { int x = Q.top().second; Q.pop(); if(vis[x]) continue; vis[x] = 1; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(dis[y] > dis[x] + 1) { dis[y] = dis[x] + 1; cnt[y] = cnt[x]; Q.push(pin(-dis[y], y)); } else if(dis[y] == dis[x] + 1) { cnt[y] += cnt[x]; } } } } int main() { // freopen("testdata.in", "r", stdin); read(n), read(m); int st, ed; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { read(a[i][j]); if(a[i][j] == 3) st = id(i, j); if(a[i][j] == 4) ed = id(i, j); } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(a[i][j] == 0 || a[i][j] == 3) { memset(ins, 0, sizeof(ins)); dfs(id(i, j), i, j); } dij(st); if(dis[ed] == inf) puts("-1"); else printf("%lld\n%lld\n", dis[ed] - 1, cnt[ed]); return 0; }