Editorial for Mê cung
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Sub 1 : có tối đa 1 quái vật trên lưới
- Vì chỉ có 1 quái vật, tất cả các vị trí đến được điểm ~exit~ đều có thỏa mãn.
- Sử dụng thuật toán ~BFS~ từ những đỉểm ~exit~ để tìm các điểm thỏa mãn.
- ĐPT: ~O(n * m)~
Sub 2 + 3 + 4 : ~m * n \le 3000~
- Vì sau khi gặp quái vật ở 1 ô thì nó sẽ biến mất nên nếu trên đường đi từ 1 ô ~(i, j)~ gặp 2 quái vật khác nhau thì ô đó sẽ không thỏa mãn.
- Điều kiện đường đi từ ô ~(i, j)~ đến ô ~(u, v)~ không gặp quái vật tương đương với việc khoảng cách từ ô ~(i, j)~ đến ~(u, v)~ bé hơn khoảng cách từ quái vật đến ~(u, v)~. Từ đây ta có thể xây dựng thuật toán cho sub này.
- Gọi ~d[k][i][j]~ là khoảng cách gần thứ ~k~ từ một ô có kí tự ~d~ đến ô ~(i, j)~ (~1~ ~\le~ i ~\le~ ~2~), ta có thể tính được mảng d bằng thuật toán ~BFS~ đa luồng từ các ô có kí tự ~d~.
- Lúc này, d[2][i][j] là khoảng cách xa nhất có mà 1 ô có thể đén được ~(i, j)~ mà không bị 2 quái vật tấn công. Như vậy ta có thể xét ~n * m~ ô trên bảng và sử dụng thuật toán ~BFS~ tìm đường đi ngắn nhất đến các ô ~(u, v)~ có giá trị ~e~. Xét ô ~(i, j)~ có khoảng cách đến ô có giá trị e ~(u, v)~ là ~x~, ô ~(i, j)~ sẽ là ô lợi thế khi ~x < d[2][u][v]~.
- ĐPT: ~O((n * m) ^ 2)~
Sub 5 : có tối đa 1 cửa thoát hiểm
- Sử dụng thuật toán như sub trên, tuy nhiên ta sẽ sử dụng thuật toán ~BFS~ từ ô cửa thoát hiểm để tìm đường đi ngắn nhất đến các đỉnh khác.
- Gọi ~f[i][j]~ là khoảng cách ngắn nhất từ ô cửa thoát hiểm ~(u, v)~ đến ô ~(i, j)~, ô ~(i, j)~ là ô lợi thế khi ~f[i][j] < d2[u][v]~.
- ĐPT: ~O(m * n)~
Sub 6 : ~n, m \le 2000~
- Có nhiều ô cửa thoát hiểm nên ta có thể sử dụng thuật toán ~Dijkstra~ đa luồng từ các ô cửa thoát hiểm và duy trì mảng ~dist[i][j]~ là khoảng cách xa nhất có thể đi tiếp từ ô ~(i, j)~. Ta có ~dist[u][v] = d[2][u][v]~ nếu ô ~(u, v)~ là cửa thoát hiểm và ~dist[u][v] = 0~ trong trường hợp còn lại. Khi ~Dijkstra~, khi đi từ ô ~(x, y)~ đến ô ~(i, j)~, ta kiểm tra ~dist[i][j] < dist[x][y] - 1~ để cập nhật/
- Lúc này, số ô có thể đến được trong quá trình ~Dijkstra~ chính là đáp án.
- ĐPT: ~O(n * m * log)~
Sub 7 : ~n, m \le 3000~
- Để khử log, ta sử dụng thuật toán ~BFS~ đa luồng. Tuy giá trị của các đỉnh nguồn là khác nhau nhưng giá trị không vượt quá ~n * m~ nên ta có thể sử dụng ~n * m~ ~queue~ để lưu các giá trị phân biệt.
- Khi cập nhật ~dist[i][j] = dist[x][y] - 1~, ta đẩy vào ô ~(i, j)~ xuống ~q[dist[x][y] - 1]~.
- Tuy nhiên nếu lưu ~queue<pải<int, int>>~ thì mảng sẽ quá giới hạn của mảng nên ta có thể nén ô ~(i, j)~ thành đỉnh ~m * (x - 1) + y~ để tiết kiệm bộ nhớ.
- ĐPT : ~O(n * m)~
Code tham khảo
#include "bits/stdc++.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
// #define int long long
const int MOD = 1e9 + 7;
const int inf = 2e9;
const int N = 3005;
int n, m;
int a[N][N];
pair<int, int> d[5] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
namespace full {
struct node {
int x, y, root, dist;
};
struct node2 {
int x, y, lim;
};
pair<int, int> mn[N][N][2];
int get_id(int x, int y) {
return m * (x - 1) + y;
}
pair<int, int> get_node(int x) {
return {(x - 1) / m + 1, (x - 1) % m + 1};
}
bool mark[N][N];
int dist[N][N];
vector<int> layer[N * N];
void solve() {
queue<node> q;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(a[i][j] == 1) {
q.push({i, j, get_id(i, j), 0});
mn[i][j][0] = {0, get_id(i, j)};
mn[i][j][1] = {inf, get_id(i, j)};
}
else mn[i][j][0] = mn[i][j][1] = {inf, 0};
}
}
while(sz(q)) {
auto cur = q.front(); q.pop();
int x = cur.x, y = cur.y, root = cur.root, dist = cur.dist;
for(int i = 0; i < 4; i++) {
int nx = x + d[i].fi, ny = y + d[i].se;
if(nx < 1 or nx > n or ny < 1 or ny > m or a[nx][ny] == 3) continue;
if(mn[nx][ny][0].fi > dist + 1) {
mn[nx][ny][1] = mn[nx][ny][0];
mn[nx][ny][0] = {dist + 1, root};
q.push({nx, ny, root, dist + 1});
} else if(mn[nx][ny][1].fi > dist + 1 and root != mn[nx][ny][0].se) {
mn[nx][ny][1] = {dist + 1, root};
q.push({nx, ny, root, dist + 1});
}
}
}
int mx = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(a[i][j] == 2) {
if(mn[i][j][1].fi == inf) mn[i][j][1].fi = n * m;
layer[mn[i][j][1].fi].pb(get_id(i, j));
mx = max(mx, mn[i][j][1].fi);
dist[i][j] = mn[i][j][1].fi;
}
}
}
for(int i = mx; i >= 0; i--) {
while(sz(layer[i])) {
auto cur = get_node(layer[i].back()); layer[i].pop_back();
int x = cur.fi, y = cur.se;
mark[x][y] = 1;
for(int j = 0; j < 4; j++) {
int nx = x + d[j].fi, ny = y + d[j].se;
if(nx < 1 or nx > n or ny < 1 or ny > m or a[nx][ny] == 3) continue;
if(dist[nx][ny] < i - 1) {
dist[nx][ny] = i - 1;
if(i > 0) layer[i - 1].pb(get_id(nx, ny));
}
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
ans += mark[i][j];
}
}
cout << ans << ln;
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#define task "MECUNG"
if(fopen(task ".INP", "r")) {
freopen(task ".INP", "r", stdin);
freopen(task ".OUT", "w", stdout);
}
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
char c; cin >> c;
if(c == 'd') a[i][j] = 1;
else if(c == 'e') a[i][j] = 2;
else if(c == '#') a[i][j] = 3;
}
}
full::solve();
cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}