Hướng dẫn giải của Mê cung
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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;
}