題目大意
給定一張 N 行 M 列的網(wǎng)格圖匈织，已知 K 格會被一直點亮』痹啵現(xiàn)在 Okabe 要從 (1, 1) 走到 (n, m) ，但必須遵守以下限制：
- 只能在被點亮的格子行走释液；
- 只能走到當前格上下左右的格子里面熏矿。
當然了，如果只能這樣的話也太困難了孝凌。因此 Okabe 可以選擇花一塊錢來點亮任意一行或者一列方咆，但需要滿足以下條件：
- 任一時刻至多有一行或一列被按照這種方式點亮
- 只能在任意一格初始被點亮的格子中間改變網(wǎng)絡的點亮狀態(tài)
- 每次取消點亮時，該行（列）所有被付費點亮的格子會被熄滅
- 取消點亮是免費的
試問 Okabe 能否到達 (n, m)蟀架，若可以瓣赂，試求最小花費。
題目保證 N, M, K 不超過 104片拍，(1, 1) 是初始被點亮的格子之一煌集。
分析
這個題的切入點比較明顯，即用邊權為 0 的邊連接每個被點亮格子與其周圍的被點亮格子捌省；用邊權為 1 的邊連接每個被點亮格子和其同行列非鄰接的被點亮格子與其相鄰行列的被點亮格子苫纤。如果 (n, m) 未被點亮則用邊權為 1 的邊連接其與其同行列的所有被點亮格子。然后判斷圖連通性并求最短路纲缓。
但是卷拘，雖然直觀上來說，這個算法對于隨機數(shù)據(jù)的表現(xiàn)還算差強人意祝高，不過對于點亮格子在同一行列這樣的極端數(shù)據(jù)栗弟，圖的邊數(shù)會與 K2 成正比。復雜度上應該無法接受工闺。所以我們需要構思其他的建圖方法使得圖的邊數(shù)與 K 成正比乍赫。
這種矩形網(wǎng)絡很容易讓人想到二分圖匹配，每個節(jié)點控制當前行及當前列陆蟆。這種構圖方式是顯然不行的雷厂。不過如果從行與列入手，不難注意到如果付費點亮某個特定行或列遍搞，那么一次點亮以后即可在該行（列）及鄰接的點亮格組成的聯(lián)通塊內(nèi)無阻免費通行罗侯。同時，我們發(fā)現(xiàn) N 和 M 與 K 同階溪猿，于是钩杰，可以添加 N 個行中轉(zhuǎn)站和 M 個列中轉(zhuǎn)站，進入這些中轉(zhuǎn)站需要付費诊县，表示點亮對應的行（列）讲弄。剩下的部分的圖的構造非常容易∫廊可以證明這種構圖方法所得的圖中邊的數(shù)量與點數(shù)成正比避除。這里要注意的一個細節(jié)是如果把構圖方式改為出中轉(zhuǎn)站需要付費而進站免費怎披，答案會在終點在非點亮格時變小。因為這種錯誤的方式可以理解為允許“透支”瓶摆。
代碼
總復雜度為 O((n + m + k) × log(n + m + k))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 11234;
int dis[maxn * 3], n, m, k;
pii pos[maxn];
map<pii, int> lis;
vector<pii> G[maxn * 3];
int main() {
scanf("%d%d%d", &n, &m, &k);
int s, t[2] = {};
reset(dis, 0x3f);
FOR(i, 1, k) {
scanf("%d%d", &pos[i]._1, &pos[i]._2);
lis[pos[i]] = i;
if (pos[i] == mp(1, 1)) s = i;
}
FOR(i, 1, k) {
int x = pos[i]._1, y = pos[i]._2;
if (lis.count(mp(x - 1, y))) G[i].eb(lis[mp(x - 1, y)], 0);
if (lis.count(mp(x + 1, y))) G[i].eb(lis[mp(x + 1, y)], 0);
if (lis.count(mp(x, y - 1))) G[i].eb(lis[mp(x, y - 1)], 0);
if (lis.count(mp(x, y + 1))) G[i].eb(lis[mp(x, y + 1)], 0);
G[i].eb(x + k, 1);
G[x + k].eb(i, 0);
G[i].eb(y + k + n, 1);
G[y + k + n].eb(i, 0);
if (x > 1) {
G[i].eb(x + k - 1, 1);
G[x + k - 1].eb(i, 0);
}
if (x < n) {
G[i].eb(x + k + 1, 1);
G[x + k + 1].eb(i, 0);
}
if (y > 1) {
G[i].eb(y + k + n - 1, 1);
G[y + k + n - 1].eb(i, 0);
}
if (y < m) {
G[i].eb(y + k + n + 1, 1);
G[y + k + n + 1].eb(i, 0);
}
}
if (lis.count(mp(n, m))) t[0] = lis[mp(n, m)];
else t[0] = k + n, t[1] = k + n + m;
set<pii> st;
st.insert(mp(0, s));
int ans = -1;
while (!st.empty()) {
auto now = *st.begin(); st.erase(st.begin());
int d = now._1, u = now._2;
if (d >= dis[u]) continue;
dis[u] = d;
if (u == t[0] || u == t[1]) {
ans = chkmax(ans, d);
break;
}
for (auto vv : G[u]) st.insert(mp(d + vv._2, vv._1));
}
printf("%d", ans);
}
