Thoát lũ (Đề tự luyện HSG Tin 9 – Bài 4) – BFS nhiều nguồn và cuộc đua giữa người và nước

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 4 (đề tự soạn) Độ khó: Khá Đồ thị BFS BFS nhiều nguồn

Đề bài

Thoát lũ

Bản đồ là lưới $N \times M$, mỗi ô là: . đất trống, # đá (người và nước đều không vào được), * ô đang có nước (có thể có nhiều ô), S vị trí thầy Sơn, E trạm cứu hộ.

Trong mỗi phút, lần lượt: (1) thầy Sơn phải di chuyển sang một trong bốn ô kề cạnh, không ra ngoài bản đồ, không vào ô đá, không vào ô đang có nước; nếu bước vào E thì được cứu ngay. (2) Sau đó nước tràn từ mỗi ô có nước sang các ô kề không phải đá; nếu ô thầy Sơn đang đứng bị nước tràn tới thì thầy Sơn gặp nguy hiểm – không được để chuyện này xảy ra.

Tính số phút ít nhất để thầy Sơn tới E an toàn, hoặc in -1 nếu không thể.

Dữ liệu vào: Dòng đầu $N, M$ $(1 \le N, M \le 1000)$, sau đó $N$ dòng mô tả bản đồ (đúng một S, một E).

Subtask:

Subtask 1 (20%): không có ô nước.
Subtask 2 (30%): $N, M \le 50$.
Subtask 3 (50%): không có ràng buộc gì thêm.

Input

3 5
S...E
####.
..*..

Output

Giải thích

Thầy Sơn đi 4 bước sang phải.
Nước cũng tới E ở phút 4
nhưng thầy Sơn đi trước nên
vẫn kịp vào trạm.

Đề trên OJ còn 2 ví dụ khác: một bản đồ không có nước (đáp án $7$) và một bản đồ mà nước chặn hết đường (đáp án $-1$).

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Thoát lũ

Lời mở đầu

Nếu không có nước, đây là bài BFS tìm đường ngắn nhất trên lưới quen thuộc. Nước làm bài khó lên ở chỗ bản đồ thay đổi theo thời gian: ô hôm nay đi được, vài phút nữa đã ngập.

Mấu chốt: nước lan không phụ thuộc gì vào thầy Sơn. Vậy ta tính trước cho mỗi ô một con số $f$ = phút nước tràn tới ô đó. Với ví dụ trên:

S7654####321012

Số trên mỗi ô là $f$: nước từ ô * lan ra mỗi phút một ô. Ô E (màu cam) bị ngập ở phút 4.

Sau đó thầy Sơn đi BFS như bình thường, chỉ thêm một điều kiện: được bước vào ô $v$ ở phút $t$ khi và chỉ khi $t < f[v]$ (nước chưa tới, và cuối phút đó nước cũng chưa tràn tới). Riêng ô $E$: Thầy Sơn được cứu ngay khi bước vào, trước khi nước tràn, nên chỉ cần $t \le f[E]$.

Cách 1BFS bỏ qua nước · 20%Cách 2Mô phỏng từng phút · 30%Cách 32 lần BFS · 100%

Cách 1Không có nước: BFS thường – O(N·M) · 20%

Subtask 1 không có ô *, nên chỉ là BFS từ $S$: mỗi ô được đưa vào hàng đợi đúng một lần, khoảng cách ô kề bằng khoảng cách ô hiện tại cộng 1. Ô $E$ chưa được thăm thì in $-1$.

#include <bits/stdc++.h>
using namespace std;

// Cach 1: khong co nuoc -> BFS thuong tu S - O(N*M): 20%
int main(){
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for(auto &s : g) cin >> s;
    vector<vector<int>> d(n, vector<int>(m, -1));
    queue<pair<int,int>> q;
    int ex = 0, ey = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            if(g[i][j] == 'S'){ d[i][j] = 0; q.push({i, j}); }
            if(g[i][j] == 'E'){ ex = i; ey = j; }
        }
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        for(int k = 0; k < 4; k++){
            int a = x + dx[k], b = y + dy[k];
            if(a < 0 || b < 0 || a >= n || b >= m) continue;
            if(g[a][b] == '#' || g[a][b] == '*' || d[a][b] != -1) continue;
            d[a][b] = d[x][y] + 1;
            q.push({a, b});
        }
    }
    cout << d[ex][ey];
    return 0;
}

# Cach 1: khong co nuoc -> BFS thuong tu S - O(N*M): 20%
import sys
from collections import deque
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [data[2 + i].decode() for i in range(n)]
d = [[-1] * m for _ in range(n)]
q = deque()
for i in range(n):
    for j in range(m):
        if g[i][j] == 'S':
            d[i][j] = 0; q.append((i, j))
        elif g[i][j] == 'E':
            ex, ey = i, j
while q:
    x, y = q.popleft()
    for a, b in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
        if 0 <= a < n and 0 <= b < m and g[a][b] not in '#*' and d[a][b] == -1:
            d[a][b] = d[x][y] + 1
            q.append((a, b))
print(d[ex][ey])

Không gian$O(N \cdot M)$

Thời gian$O(N \cdot M)$

Có nước thì code này sai ngay, vì nó cho thầy Sơn đi qua những ô sẽ bị ngập trước khi thầy Sơn tới.

Cách 2Mô phỏng từng phút – O(T·N·M) · 30%

Làm đúng như đề kể: giữ tập các ô thầy Sơn có thể đang đứng. Mỗi phút: (1) cho thầy Sơn bước sang các ô kề chưa ngập; (2) quét cả bảng để nước tràn thêm một ô; (3) bỏ các ô thầy Sơn đứng mà vừa bị ngập.

#include <bits/stdc++.h>
using namespace std;

// Cach 2: mo phong tung phut, moi phut quet ca bang de loang nuoc - O(T*N*M): 30%
int main(){
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for(auto &s : g) cin >> s;
    vector<vector<char>> wet(n, vector<char>(m, 0)), seen(n, vector<char>(m, 0));
    vector<pair<int,int>> cur;           // cac o An co the dang dung
    int ex = 0, ey = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            if(g[i][j] == '*') wet[i][j] = 1;
            if(g[i][j] == 'S'){ cur.push_back({i, j}); seen[i][j] = 1; }
            if(g[i][j] == 'E'){ ex = i; ey = j; }
        }
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    for(int t = 1; !cur.empty(); t++){
        // 1) An di truoc
        vector<pair<int,int>> nxt;
        for(auto [x, y] : cur)
            for(int k = 0; k < 4; k++){
                int a = x + dx[k], b = y + dy[k];
                if(a < 0 || b < 0 || a >= n || b >= m) continue;
                if(g[a][b] == '#' || wet[a][b] || seen[a][b]) continue;
                if(a == ex && b == ey){ cout << t; return 0; }
                seen[a][b] = 1;
                nxt.push_back({a, b});
            }
        // 2) nuoc tran: quet toan bo bang
        vector<vector<char>> w2 = wet;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) if(wet[i][j])
                for(int k = 0; k < 4; k++){
                    int a = i + dx[k], b = j + dy[k];
                    if(a >= 0 && b >= 0 && a < n && b < m && g[a][b] != '#') w2[a][b] = 1;
                }
        wet = w2;
        // 3) bo cac o vua bi ngap
        cur.clear();
        for(auto [x, y] : nxt) if(!wet[x][y]) cur.push_back({x, y});
    }
    cout << -1;
    return 0;
}

# Cach 2: mo phong tung phut, moi phut quet ca bang de loang nuoc - O(T*N*M): 30%
import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [data[2 + i].decode() for i in range(n)]
wet = [[g[i][j] == '*' for j in range(m)] for i in range(n)]
seen = [[False] * m for _ in range(n)]
cur = []
for i in range(n):
    for j in range(m):
        if g[i][j] == 'S':
            cur.append((i, j)); seen[i][j] = True
        elif g[i][j] == 'E':
            ex, ey = i, j
ans = -1
t = 0
while cur and ans == -1:
    t += 1
    nxt = []
    for x, y in cur:
        for a, b in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            if 0 <= a < n and 0 <= b < m and g[a][b] != '#' and not wet[a][b] and not seen[a][b]:
                if (a, b) == (ex, ey):
                    ans = t
                seen[a][b] = True
                nxt.append((a, b))
    if ans != -1:
        break
    w2 = [row[:] for row in wet]
    for i in range(n):
        for j in range(m):
            if wet[i][j]:
                for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                    if 0 <= a < n and 0 <= b < m and g[a][b] != '#':
                        w2[a][b] = True
    wet = w2
    cur = [(x, y) for x, y in nxt if not wet[x][y]]
print(ans)

Thời gian: mỗi phút quét cả bảng $O(N \cdot M)$, số phút $T$ có thể tới cỡ $N \cdot M / 2$ (đường đi ngoằn ngoèo kiểu "con rắn"). Với $50 \times 50$ là khoảng $3 \cdot 10^6$ phép tính – ổn. Nhưng với $1000 \times 1000$ là $5 \cdot 10^{11}$ ⇒ quá thời gian.

Không gian$O(N \cdot M)$

Thời gian$O(T \cdot N \cdot M)$

Cách 2 + Cách 1 = 50 điểm

Cách 2 bị quá thời gian ở các test lớn của subtask 1 (mê cung con rắn $999 \times 1000$), nên nếu chỉ làm được tới đây thì nên viết thêm: không có * thì chạy BFS thường của cách 1.

Cách 3BFS nhiều nguồn cho nước, rồi BFS cho thầy Sơn – O(N·M) · 100%

Hai lần BFS

Lần 1 (nước): đưa tất cả các ô * vào hàng đợi cùng lúc với $f = 0$ rồi BFS như thường. Đây gọi là BFS nhiều nguồn: kết quả $f[v]$ là khoảng cách từ $v$ tới nguồn nước gần nhất, đúng bằng phút nước tràn tới $v$.
Lần 2 (thầy Sơn): BFS từ $S$. Từ ô $u$ (thầy Sơn tới ở phút $d[u]$) sang ô kề $v$ ở phút $t = d[u] + 1$ khi $t < f[v]$, hoặc $t \le f[E]$ nếu $v$ là ô $E$.

Vì sao BFS vẫn đúng khi có điều kiện thời gian? Vì đến một ô sớm hơn bao giờ cũng tốt hơn (nước chỉ lan thêm, không bao giờ rút), và BFS luôn đến mỗi ô ở thời điểm sớm nhất có thể. Các bạn bấm từng phút ở khung dưới để thấy nước và thầy Sơn "chạy đua":

Bản đồ (mỗi dòng một hàng)

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

// Cach 3: BFS nhieu nguon cho nuoc, roi BFS cho An - O(N*M): 100%
const int INF = INT_MAX;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for(auto &s : g) cin >> s;
    vector<vector<int>> f(n, vector<int>(m, INF));   // f = phut nuoc tran toi
    vector<vector<int>> d(n, vector<int>(m, -1));    // d = phut An toi
    queue<pair<int,int>> q;
    int sx = 0, sy = 0, ex = 0, ey = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            if(g[i][j] == '*'){ f[i][j] = 0; q.push({i, j}); }  // moi nguon nuoc vao hang doi
            if(g[i][j] == 'S'){ sx = i; sy = j; }
            if(g[i][j] == 'E'){ ex = i; ey = j; }
        }
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    // BFS 1: nuoc
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        for(int k = 0; k < 4; k++){
            int a = x + dx[k], b = y + dy[k];
            if(a < 0 || b < 0 || a >= n || b >= m || g[a][b] == '#') continue;
            if(f[a][b] == INF){ f[a][b] = f[x][y] + 1; q.push({a, b}); }
        }
    }
    // BFS 2: An. Buoc vao o (a,b) o phut t can t < f[a][b]; rieng o E chi can t <= f[E]
    d[sx][sy] = 0; q.push({sx, sy});
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        if(x == ex && y == ey) break;
        for(int k = 0; k < 4; k++){
            int a = x + dx[k], b = y + dy[k];
            if(a < 0 || b < 0 || a >= n || b >= m || g[a][b] == '#' || d[a][b] != -1) continue;
            int t = d[x][y] + 1;
            bool ok = (a == ex && b == ey) ? (t <= f[a][b]) : (t < f[a][b]);
            if(ok){ d[a][b] = t; q.push({a, b}); }
        }
    }
    cout << d[ex][ey];
    return 0;
}

# Cach 3: BFS nhieu nguon cho nuoc, roi BFS cho An - O(N*M): 100%
import sys
from collections import deque
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [data[2 + i].decode() for i in range(n)]
INF = float('inf')
f = [[INF] * m for _ in range(n)]
d = [[-1] * m for _ in range(n)]
q = deque()
for i in range(n):
    for j in range(m):
        c = g[i][j]
        if c == '*':
            f[i][j] = 0; q.append((i, j))
        elif c == 'S':
            sx, sy = i, j
        elif c == 'E':
            ex, ey = i, j
while q:                                   # BFS 1: nuoc
    x, y = q.popleft()
    for a, b in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
        if 0 <= a < n and 0 <= b < m and g[a][b] != '#' and f[a][b] == INF:
            f[a][b] = f[x][y] + 1
            q.append((a, b))
d[sx][sy] = 0; q.append((sx, sy))
while q:                                   # BFS 2: An
    x, y = q.popleft()
    if (x, y) == (ex, ey):
        break
    for a, b in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
        if 0 <= a < n and 0 <= b < m and g[a][b] != '#' and d[a][b] == -1:
            t = d[x][y] + 1
            if (t <= f[a][b]) if (a, b) == (ex, ey) else (t < f[a][b]):
                d[a][b] = t
                q.append((a, b))
print(d[ex][ey])

Các bạn bấm chạy tay code C++ để xem từng dòng nhé (ở phần BFS lần 2, mỗi ô ghi dạng f|d):

C++▶ Chạy tay từng dòng codeCách 3: BFS nước từ mọi ô * cùng lúc, rồi BFS thầy Sơn với điều kiện t < f (riêng E: t ≤ f).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4// Cach 3: BFS nhieu nguon cho nuoc, roi BFS cho An - O(N*M): 100%

5const int INF = INT_MAX;

6int main(){

7 ios::sync_with_stdio(false); cin.tie(nullptr);

8 int n, m;

9 cin >> n >> m;

10 vector<string> g(n);

11 for(auto &s : g) cin >> s;

12 vector<vector<int>> f(n, vector<int>(m, INF)); // f = phut nuoc tran toi

13 vector<vector<int>> d(n, vector<int>(m, -1)); // d = phut An toi

14 queue<pair<int,int>> q;

15 int sx = 0, sy = 0, ex = 0, ey = 0;

16 for(int i = 0; i < n; i++)

17 for(int j = 0; j < m; j++){

18 if(g[i][j] == '*'){ f[i][j] = 0; q.push({i, j}); } // moi nguon nuoc vao hang doi

19 if(g[i][j] == 'S'){ sx = i; sy = j; }

20 if(g[i][j] == 'E'){ ex = i; ey = j; }

21 }

22 int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

23 // BFS 1: nuoc

24 while(!q.empty()){

25 auto [x, y] = q.front(); q.pop();

26 for(int k = 0; k < 4; k++){

27 int a = x + dx[k], b = y + dy[k];

28 if(a < 0 || b < 0 || a >= n || b >= m || g[a][b] == '#') continue;

29 if(f[a][b] == INF){ f[a][b] = f[x][y] + 1; q.push({a, b}); }

30 }

31 }

32 // BFS 2: An. Buoc vao o (a,b) o phut t can t < f[a][b]; rieng o E chi can t <= f[E]

33 d[sx][sy] = 0; q.push({sx, sy});

34 while(!q.empty()){

35 auto [x, y] = q.front(); q.pop();

36 if(x == ex && y == ey) break;

37 for(int k = 0; k < 4; k++){

38 int a = x + dx[k], b = y + dy[k];

39 if(a < 0 || b < 0 || a >= n || b >= m || g[a][b] == '#' || d[a][b] != -1) continue;

40 int t = d[x][y] + 1;

41 bool ok = (a == ex && b == ey) ? (t <= f[a][b]) : (t < f[a][b]);

42 if(ok){ d[a][b] = t; q.push({a, b}); }

43 }

44 }

45 cout << d[ex][ey];

46 return 0;

47}

Không gian$O(N \cdot M)$

Thời gian$O(N \cdot M)$

Ba cái bẫy trong bộ test

Hòa ở ô E: dùng chung điều kiện t < f cho cả ô $E$ thì sai ở các test thầy Sơn và nước tới $E$ cùng phút (ví dụ 3 của đề). Bộ test có cả bản đồ $1000 \times 1000$ dạng con rắn mà nước tới $E$ đúng lúc thầy Sơn tới.
Dùng t <= f cho mọi ô: cho thầy Sơn đứng ở ô sẽ bị ngập ngay cuối phút đó. Có test "ngã tư" mà nước đổ vào đúng lúc thầy Sơn đi qua.
Chỉ BFS từ một nguồn nước hoặc BFS từng nguồn rồi lấy min (chậm $K$ lần): có test nhiều nguồn mà nguồn nguy hiểm nhất nằm cuối bản đồ.

Bộ test chấm "bắt" những lỗi nào?

Cách làm	Sub 1	Sub 2	Sub 3	Điểm
Cách 1 – bỏ qua nước	Đúng	Sai	Sai	20
Cách 2 – mô phỏng từng phút	TLE	Đúng	TLE	30
Cách 3 nhưng ô E cũng dùng `t < f`	Đúng	Sai	Sai	20
Cách 3 nhưng mọi ô dùng `t <= f`	Đúng	Sai	Sai	20
Cách 3 nhưng chỉ loang từ một nguồn nước	Đúng	Sai	Sai	20
Cách 3 đầy đủ	Đúng	Đúng	Đúng	100

Ghi chú của mình: các code C++ đã được nộp thử trên ClueOJ với đúng bộ test của bài: cách 1 được 20 điểm, cách 2 được 30 điểm, bản sai trường hợp hòa ở E được 20 điểm, cách 3 được 100 điểm (test lớn nhất khoảng 0.05 giây). Bản Python của cách 3 cho kết quả đúng nhưng với bản đồ $1000 \times 1000$ chạy mất vài giây, đi thi các bạn nên dùng C++.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Tự học thuật toán: khó ở đâu?

Đọc xong một bài giải là bước đầu. Phần lớn học sinh tự học sẽ gặp những trở ngại sau:

Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
Dễ nản giữa chừng khi không có ai theo sát.

Học cùng thầy Nam Sơn, các trở ngại đó được gỡ bỏ:

Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.

Xem chi tiết khóa học Nhắn Zalo hỏi thầy

Lập Trình Thuật Toán

Thoát lũ (Đề tự luyện HSG Tin 9 – Bài 4) – BFS nhiều nguồn và cuộc đua giữa người và nước

Đề bài

Lời mở đầu

Cách 1Không có nước: BFS thường – O(N·M) · 20%

Cách 2Mô phỏng từng phút – O(T·N·M) · 30%

Cách 3BFS nhiều nguồn cho nước, rồi BFS cho thầy Sơn – O(N·M) · 100%

Bộ test chấm "bắt" những lỗi nào?

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++