Hướng dẫn giải của Bedao Regular Contest 01 - HGRAPH
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.
Tác giả:
Nhận xét: Xem mỗi ô trong mê cung là ~1~ đỉnh của đồ thị, với mỗi ô ~(i, j)~ chúng ta xây cạnh đến các ô mà từ ~(i, j)~ có thể đến trong ~1~ bước di chuyển. Nếu đồ thị mà mọi cạnh có chung trọng số thì có thể sử dụng thuật toán BFS để tìm đường đi ngắn nhất giữa ~2~ đỉnh, dễ thấy đồ thị trong bài thỏa mãn điều kiện trên với trọng số chung là ~1~. Vậy ta chỉ cần dựng được đồ thị thì có thể giải quyết được bài toán.
Tuy nhiên, độ phức tạp của thuật toán BFS là ~O(n+m)~ với đồ thị ~n~ đỉnh ~m~ cạnh dẫn đến chúng ta cần chứng minh rằng số cạnh đủ nhỏ để chạy BFS trong ~1~ giây. Nếu bạn không tỉnh táo sẽ bị vướng ở bước này.
Chứng minh số cạnh trên đồ thị ~\leq~ ~8\times N \times M~:
- Nếu ô ~(i, j)~ không phải cột đá thì có tối đa:
~4~ cạnh từ các cột đá gần nhất ở mỗi hướng Đông Tây Nam Bắc đến ô ~(i, j)~
~4~ cạnh từ ~(i, j)~ đến các ô ~(i−1, j), (i, j+1), (i+1, j), (i, j−1)~
- Nếu ô ~(i, j)~ là cột đá thì có tối đa:
~4~ cạnh từ ô ~(i, j)~ đến các cột đá gần nhất ở mỗi hướng Đông Tây Nam Bắc
- Do mê cung gồm ~N \times M~ ô thuộc ~2~ trường hợp trên, hiển nhiên đồ thị có không quá ~8 \times N \times M~ cạnh
Code mẫu
#include <bits/stdc++.h> using namespace std; #define int ll #define vt vector #define TASK "" #define pb push_back #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define f first #define s second #define MASK(i) (1ll << (i)) #define BIT(x, i) (((x) >> (i)) & 1ll) #define builtin_popcount __builtin_popcountll #define Times cerr <<"\nTime: "<<clock()/(double)1000<<" sec" // cout << setprecision(0) << fixed << ans; #define FOR(i, l, r) for (int i = (l); i <= (r); ++i) #define rep(i, r, l) for (int i = (r); i >= (l); --i) // Dang Quoc Cuong 196 147 :>> typedef long long ll; typedef pair<int,int> ii; typedef pair<int, ii> iii; const int INF = 1e9; const int mod = 1e9 + 7; const int N = 2e3 + 5; const int Sz = 1e6 + 5; const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; void setIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(TASK".inp","r")) { freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout); } } /***------------------------- END ---------------------------***/ int n, m, a[N][N], dis[N][N], ans, k; queue<ii> Q; bool inside(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } void add(int u, int v, int x, int y) { if (inside(x, y) && dis[x][y] == 0) { dis[x][y] = dis[u][v] + 1; Q.push(ii(x, y)); } } void bfs() { Q.push(ii(1, 1)); dis[1][1] = 1; while (sz(Q)) { ii u = Q.front(); Q.pop(); if (u == ii(n, m)) { ans = dis[n][m] - 1; return; } if (!a[u.f][u.s]) { FOR(i, 0, 3) { int vx = u.f + dx[i], vy = u.s + dy[i]; add(u.f, u.s, vx, vy); } } else { FOR(i, 0, 3) { FOR(j, 1, k) { int vx = u.f + dx[i]*j, vy = u.s + dy[i]*j; add(u.f, u.s, vx, vy); if (a[vx][vy]) break; } } } } } void test_case() { cin >> n >> m; k = max(n, m); FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j]; bfs(); cout << ans; } signed main() { setIO(); int TC = 1; while (TC--) { test_case(); } return 0; } /*** quoccuong ***/
Bình luận