Du Hành (ACM Việt Nam 10-2014)

Nguồn: ACM Việt Nam 10-2014 (Codeforces Gym 100541 – I) Độ khó: Khá Quy hoạch động QHĐ trên lưới Đệ quy có nhớ

Đề bài

Du hành

Alpha Centauri-M (ACM) là một hành tinh với rất nhiều cảnh đẹp cho du khách từ Trái đất. Bản đồ của ACM được chia thành một lưới gồm $M$ dòng, $N$ cột. Các cột được đánh số từ $1$ đến $N$ theo chiều từ trái sang phải. Các dòng được đánh số từ $1$ đến $M$ theo chiều từ trên xuống dưới. Có một vài ô của lưới là núi lửa nên không thể viếng thăm được. Các ô còn lại gọi là ô an toàn.

Khi tiến đến ACM, phi thuyền sẽ hạ cánh tại một ô an toàn nào đó. Sau đó du khách sẽ viếng thăm hành tinh bằng xe tự hành. Bắt đầu từ ô hạ cánh $(r_0, c_0)$, xe tự hành có thể đi đến bốn ô lân cận là $(r_0 - 1, c_0)$, $(r_0 + 1, c_0)$, $(r_0, c_0 - 1)$, $(r_0, c_0 + 1)$. Sau đó xe tự hành sẽ tiếp tục di chuyển theo quy tắc sau:

1. Quẹo phải và tiến đến 1 ô.
2. Quẹo trái và tiến đến 1 ô.
3. Thực hiện lại bước 1.

Xe tự hành chỉ có thể viếng thăm ô an toàn, vì vậy nó sẽ dừng lại nếu ô kế tiếp là không an toàn hoặc đi ra ngoài bản đồ. Hình bên dưới minh họa một bản đồ gồm $M = 6$ dòng và $N = 7$ cột. Từ ô hạ cánh là ô $(4, 3)$, bạn có thể viếng thăm $16$ ô, kể cả ô hạ cánh.

Hình minh hoạ của đề: ngôi sao là ô hạ cánh (Landing Cell), ô sẫm màu là núi lửa (Mountain/Volcano), các mũi tên là 4 con đường của xe tự hành.

Nhiệm vụ của bạn là tìm ô hạ cánh sao cho có thể viếng thăm nhiều ô nhất của Alpha Centauri-M.

Dữ liệu nhập:

• Dòng đầu tiên là hai số nguyên $M$, $N$ cách nhau một khoảng trắng $(1 \le M, N \le 1000)$.
• Trong $M$ dòng tiếp theo, mỗi dòng chứa các số $0$, $1$ thể hiện tình trạng bản đồ ($1$ là ô an toàn, $0$ là ô không an toàn), các số xếp sát nhau.

Dữ liệu xuất: Là số nguyên xác định số lượng ô có thể thăm nhiều nhất.

Subtask:

• $20\%$ số test đầu tiên có $m, n \le 10$.
• $30\%$ số test tiếp theo có $m, n \le 100$.
• $20\%$ số test tiếp theo có $m, n \le 500$.
• $30\%$ số test còn lại không có giới hạn gì thêm.

Ví dụ 1 – input

3 3
011
111
111

Output

8

Ví dụ 2 – input

6 7
1101011
0111111
1111101
1111111
1111110
0111111

Output

20

Lưu ý định dạng trên Codeforces Gym

Bản trên Codeforces Gym (bài I – Space Tour) có nhiều bộ test trong một file: dòng đầu tiên là số bộ test $T$ ($T \le 20$), sau đó là $T$ bộ dữ liệu như trên; với mỗi bộ in đáp án trên một dòng (giới hạn 2 giây, 256 MB). Ví dụ của Codeforces chính là 2 ví dụ ở trên gộp lại: dòng đầu là 2, đáp án là 8 và 20. Code bên dưới của mình đọc theo định dạng có $T$ này. Còn trên CLUE OJ mỗi file test chỉ có 1 bộ dữ liệu (không có dòng $T$) đúng như đề ở trên, nên khi nộp CLUE em bỏ dòng đọc t và vòng while(t--), chỉ gọi init(); solve(); một lần là được.

Lời mở đầu

Bài này là bài I trong đề thi ACM Việt Nam vòng quốc gia tháng 10 năm 2014. Đề nhìn hình thì rối mắt vậy thôi chứ khi nắm được một nhận xét quan trọng thì bài trở nên rất gọn gàng, và đây cũng là một bài rất hay để luyện cách "nâng cấp" từ vét cạn lên đệ quy có nhớ rồi lên quy hoạch động bottom up. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Trước tiên mình tóm tắt lại đề một cách đơn giản nhất cho bạn nào chưa hiểu. Ta có một bản đồ $m$ dòng, $n$ cột; ô có giá trị $1$ là ô an toàn, ô có giá trị $0$ là núi lửa. Ta được hạ cánh ở một ô an toàn bất kỳ $(r_0, c_0)$. Từ đó xe tự hành đi theo 4 hướng: lên trên, sang trái, sang phải, xuống dưới. Ở mỗi hướng, sau khi tiến vào ô đầu tiên, xe cứ quẹo phải 1 ô, quẹo trái 1 ô, quẹo phải 1 ô, quẹo trái 1 ô… – tức là đi theo hình bậc thang – cho tới khi ô kế tiếp là núi lửa hoặc ra ngoài bản đồ thì dừng. Đếm tất cả các ô đi được (tính cả ô hạ cánh), và ta cần chọn ô hạ cánh sao cho con số này lớn nhất.

Với ví dụ 1 ($m = n = 3$), đáp án là $8$: ta hạ cánh ở ô $(2, 2)$ (ô giữa). Đi lên trên được $2$ ô: $(1, 2)$ rồi quẹo phải sang $(1, 3)$. Sang trái được $1$ ô: $(2, 1)$, vì ô kế tiếp (quẹo phải từ hướng trái là đi lên) là $(1, 1)$ – núi lửa. Sang phải được $2$ ô: $(2, 3)$, $(3, 3)$. Xuống dưới được $2$ ô: $(3, 2)$, $(3, 1)$. Cộng thêm chính ô hạ cánh: $2 + 1 + 2 + 2 + 1 = 8$ ô. Với ví dụ 2 thì ở hình của đề, hạ cánh tại $(4, 3)$ được $16$ ô, nhưng hạ cánh tại $(4, 4)$ thì được tận $20$ ô – các bạn kéo xuống phần minh hoạ bên dưới để tự bấm xem nhé.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn mọi ô hạ cánh · TLECách 2Đệ quy có nhớ (top down) · O(M·N) · ACCách 3QHĐ bottom up · O(M·N) · đọc thêm

Cách 1Vét cạn: thử hạ cánh ở mọi ô

Cách làm đơn giản nhất của bài này chính là vét cạn, tức là thử mọi trường hợp có thể. Vì ta có thể hạ cánh ở một ô an toàn bất kỳ, nên ta sẽ thử hạ cánh ở mọi ô an toàn, tính xem nếu hạ ở ô đó thì đi được bao nhiêu ô, rồi so sánh với biến kết quả để cập nhật. Đó là cách làm đơn giản nhất rồi.

Nhận xét quan trọng: 4 con đường không bao giờ cắt nhau

Các bạn nhìn hình của đề sẽ thấy rõ: con đường đi lên trên chạy về phía trên – phải, con đường sang trái chạy về phía trên – trái, sang phải chạy về phía dưới – phải, xuống dưới chạy về phía dưới – trái. Mỗi con đường nằm gọn trong một "góc phần tư" riêng quanh ô hạ cánh nên chúng không có điểm chung (không trùng, không cắt nhau). Điều này cực kỳ quan trọng, vì nhờ vậy ta không cần lo đếm trùng ô, mà chỉ cần cộng thẳng:

Số ô đi được khi hạ cánh tại (r0, c0)

(số ô đi được khi đi lên trên) + (số ô khi đi sang trái) + (số ô khi đi sang phải) + (số ô khi đi xuống dưới) + $1$
Cộng thêm $1$ ở cuối vì chính ô hạ cánh cũng được tính là 1 ô đi được.

Minh hoạ 4 con đường bậc thang

Các bạn nhập bản đồ (mỗi dòng cách nhau một khoảng trắng), chọn ô hạ cánh rồi bấm Tiếp để xem xe tự hành đi từng ô theo từng hướng. Để ý các ô bên ngoài bản đồ mình vẽ nét đứt – lát nữa các bạn sẽ thấy vì sao mình vẽ chúng ra 😉.

Bản đồ r0 c0

Ví dụ nhanh:

Hàm Try(dir, i, j)

Giờ ta cần một hàm giúp ta biết được số ô có thể đi được nếu đang đi về 1 trong 4 hướng và bắt đầu từ ô $(i, j)$. Anh em lưu ý: ô $(i, j)$ là ô đầu tiên của hướng đi ta chọn. Tức là nếu hạ cánh ở $(r_0, c_0)$ và đi lên trên thì $(i, j) = (r_0 - 1, c_0)$; đi sang trái thì $(i, j) = (r_0, c_0 - 1)$; sang phải thì $(i, j) = (r_0, c_0 + 1)$; xuống dưới thì $(i, j) = (r_0 + 1, c_0)$. Chứ KHÔNG phải $(i, j) = (r_0, c_0)$ đâu nha.

Để viết một hàm chạy được cả 4 hướng cho gọn, mình quy ước theo chiều từ trên xuống dưới, từ trái sang phải:

0: đi lên trên1: đi sang trái2: đi sang phải3: đi xuống dưới

Gọi hàm Try(dir, i, j) trả về số ô ta có thể đi được theo hướng dir (direction – hướng đi, $0 \le dir \le 3$) bắt đầu từ ô $(i, j)$.

Điều kiện dừng. Mình hay khuyên anh em khai báo mảng thừa ra (thường mình $+5$), và ở bài này việc đó vô cùng quan trọng: nó làm điều kiện dừng trở nên cực kỳ đơn giản. Nếu khai báo mảng vừa khít thì trước khi truy cập a[i][j] ta phải kiểm tra $1 \le i \le m$ và $1 \le j \le n$, nếu không sẽ truy cập vào vùng bộ nhớ không khai báo; rồi mới kiểm tra ô đó có phải núi lửa không.

Nhưng bài này hay ở chỗ: khi ta khai báo a[1005][1005] là mảng toàn cục thì mọi phần tử tự động bằng $0$. Ta đọc bản đồ vào vùng hàng $1..m$, cột $1..n$, nên vùng bên ngoài – hàng $0$, cột $0$, hàng $m + 1$, cột $n + 1$ – vẫn tồn tại và đều bằng $0$, tức là núi lửa! Vậy ta đã quy việc "đi ra ngoài bản đồ" về việc "gặp núi lửa" (chính là các ô nét đứt trong khung minh hoạ ở trên đó các bạn). Điều kiện dừng chỉ còn đúng một ý:

Điều kiện dừng

if(!a[i][j]) return 0; – ô núi lửa (hoặc ngoài bản đồ) thì không đi được ô nào.

if(!a[i][j]) là cách viết gọn của if(a[i][j] == 0). Trong lập trình, nếu đem một biến ra làm điều kiện mà không ghi phép so sánh, ví dụ if(x), thì hiểu là if(x != 0). Thêm dấu ! (toán tử phủ định) đằng trước thì đảo ngược lại, tức if(!x) ⇔ if(x == 0). Vì vậy ta cần khai báo a toàn cục và thừa ra ít nhất $2$ ([1000 + 2][1000 + 2]) để có hàng $0$, cột $0$, hàng $m + 1$, cột $n + 1$; mình thì quen khai báo [1000 + 5][1000 + 5].

Xử lý chạy. Qua được điều kiện dừng thì ô $(i, j)$ là ô an toàn, ta đã đi được ít nhất 1 ô. Giờ xét từng hướng:

1/ Đi lên trên (dir = 0). Ta đang ở ô $(i, j) = (r_0 - 1, c_0)$ – ô ngay trên ngôi sao. Lưu ý trong cả quá trình này hướng đi luôn là "đi lên trên", dù đang ở bước 1 hay bước 2 (có thể bước 2 – quẹo trái – mới là bước đưa ta lên hàng trên). Mình quy ước vậy vì ban đầu ta chỉ xét 4 hướng; nếu mỗi hướng lại sinh ra hướng con thì vô cùng phức tạp.

Giờ ta cần gọi đệ quy sao cho nó lặp lại y xì trạng thái hiện tại. Ta đang ở $(i, j)$ và sắp làm bước 1 (quẹo phải): sang ô $(i, j + 1)$. Sau đó bước 2 (quẹo trái): sang ô $(i - 1, j + 1)$. Tại ô mới này ta lại làm bước 1, và hướng vẫn là đi lên trên – giống hệt trạng thái ở $(i, j)$. Vậy ta gọi đệ quy tại $(i - 1, j + 1)$, với điều kiện ô $(i, j + 1)$ phải an toàn (phải đi qua nó mới tới được ô kia mà):

if(dir == 0 && a[i][j + 1]) return Try(dir, i - 1, j + 1) + 2;

Tại sao $+2$? Vì ta đã đi được 2 ô chắc chắn là $(i, j)$ và $(i, j + 1)$, cộng với số ô đi được tiếp từ $(i - 1, j + 1)$ theo hướng lên trên. Còn nếu ô $(i - 1, j + 1)$ là núi lửa thì sao? Không cần lo, điều kiện dừng của Try lo rồi: nó trả về $0$, kết quả là $0 + 2 = 2$, đúng 2 ô $(i, j)$ và $(i, j + 1)$. Còn nếu $(i, j + 1)$ là núi lửa thì không gọi đệ quy nữa, ta chỉ đi được đúng 1 ô $(i, j)$.

2/, 3/, 4/ – các hướng còn lại làm y như vậy, chỉ khác ô "bước 1" và ô gọi đệ quy:

Hướng	Ô (i, j) đầu tiên	Bước 1 (phải an toàn)	Gọi đệ quy tại	Câu lệnh
0 – lên trên	$(r_0 - 1, c_0)$	$(i, j + 1)$	$(i - 1, j + 1)$	if(dir == 0 && a[i][j + 1]) return Try(dir, i - 1, j + 1) + 2;
1 – sang trái	$(r_0, c_0 - 1)$	$(i - 1, j)$	$(i - 1, j - 1)$	if(dir == 1 && a[i - 1][j]) return Try(dir, i - 1, j - 1) + 2;
2 – sang phải	$(r_0, c_0 + 1)$	$(i + 1, j)$	$(i + 1, j + 1)$	if(dir == 2 && a[i + 1][j]) return Try(dir, i + 1, j + 1) + 2;
3 – xuống dưới	$(r_0 + 1, c_0)$	$(i, j - 1)$	$(i + 1, j - 1)$	if(dir == 3 && a[i][j - 1]) return Try(dir, i + 1, j - 1) + 2;

Nếu không có if nào đúng thì return 1;. Ở đây mình return luôn trong từng if cho gọn (khi một if đúng thì chắc chắn kết quả là Try(...) + 2, khỏi phải kiểm tra các trường hợp sau). Anh em nào thấy dễ hiểu hơn thì có thể dùng biến cnt = 1 rồi gán cnt = Try(...) + 2 trong từng if, cuối hàm return cnt; – kết quả như nhau.

Có hàm Try rồi thì ta duyệt qua mọi ô; ô nào an toàn thì số ô đi được khi hạ cánh ở đó là

Công thức cho mỗi ô hạ cánh

$sum = Try(0, r_0 - 1, c_0) + Try(1, r_0, c_0 - 1) + Try(2, r_0, c_0 + 1) + Try(3, r_0 + 1, c_0) + 1$, rồi res = max(res, sum). Cũng chẳng phải lo $r_0 - 1$, $c_0 + 1$… bị tràn mảng, vì ta đã khai báo thừa và vùng ngoài bản đồ đều là $0$.

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

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const int maxNM = 1005;
int m, n;
bool a[maxNM][maxNM];

void init() {
    memset(a, 0, sizeof(a));
    cin >> m >> n;
    string s;
    for(int i = 1; i <= m; ++i) {
        cin >> s;
        for(int j = 0; j < n; ++j) {
            a[i][j + 1] = (int)s[j] - 48;
        }
    }
}

// 0: up; 1: left; 2: right; 3: down.
int Try(int dir, int i, int j) {
    if(!a[i][j]) return 0;
    if(dir == 0 && a[i][j + 1]) {
        return Try(dir, i - 1, j + 1) + 2;
    }
    if(dir == 1 && a[i - 1][j]) {
        return Try(dir, i - 1, j - 1) + 2;
    }
    if(dir == 2 && a[i + 1][j]) {
        return Try(dir, i + 1, j + 1) + 2;
    }
    if(dir == 3 && a[i][j - 1]) {
        return Try(dir, i + 1, j - 1) + 2;
    }
    return 1;
}

int solve() {
    int res = 0;
    for(int r0 = 1; r0 <= m; ++r0) {
        for(int c0 = 1; c0 <= n; ++c0) {
            if(a[r0][c0]) {
                int sum = Try(0, r0 - 1, c0) + Try(1, r0, c0 - 1) + Try(2, r0, c0 + 1) + Try(3, r0 + 1, c0) + 1;
                res = max(res, sum);
            }
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        init();
        cout << solve() << endl;
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)


def Try(d, i, j):
    # 0: up; 1: left; 2: right; 3: down.
    if not a[i][j]:
        return 0
    if d == 0 and a[i][j + 1]:
        return Try(d, i - 1, j + 1) + 2
    if d == 1 and a[i - 1][j]:
        return Try(d, i - 1, j - 1) + 2
    if d == 2 and a[i + 1][j]:
        return Try(d, i + 1, j + 1) + 2
    if d == 3 and a[i][j - 1]:
        return Try(d, i + 1, j - 1) + 2
    return 1


data = sys.stdin.read().split()
t = int(data[0])
p = 1
out = []
for _ in range(t):
    m, n = int(data[p]), int(data[p + 1])
    p += 2
    # bản đồ có viền 0 bao quanh: hàng 0, hàng m + 1, cột 0, cột n + 1
    a = [[0] * (n + 2) for _ in range(m + 2)]
    for i in range(1, m + 1):
        s = data[p]
        p += 1
        for j in range(n):
            a[i][j + 1] = ord(s[j]) - 48
    res = 0
    for r0 in range(1, m + 1):
        for c0 in range(1, n + 1):
            if a[r0][c0]:
                s = Try(0, r0 - 1, c0) + Try(1, r0, c0 - 1) + Try(2, r0, c0 + 1) + Try(3, r0 + 1, c0) + 1
                res = max(res, s)
    out.append(str(res))
print("\n".join(out))

Giải thích 1 số chỗ trong code:

1. const int maxNM = 1005; chính là giá trị tối đa của $n$ và $m$, mình đã cộng thêm $5$.
2. Hàm init() để đọc đầu vào. Vì trong 1 dòng các số $0$, $1$ viết liền nhau nên phải đọc bằng string, rồi duyệt từng ký tự để tách ra. string lưu từ vị trí $0$ nên mình duyệt $j$ từ $0$ tới $n - 1$, còn bản đồ thì lưu từ cột $1$ tới $n$ nên phải là a[i][j + 1]. (int)s[j] - 48 chính là (int)s[j] - (int)'0', đổi ký tự '0'/'1' thành số $0$/$1$.
3. Hàm solve() đi duyệt từng vị trí để tìm và trả về đáp án.
4. Bài trên Codeforces có nhiều test nên ta có vòng lặp chạy $T$ lần, bên trong gọi init() và solve() – 2 hàm này chỉ xử lý cho 1 bộ test.

Nhiều test thì phải xoá bản đồ cũ!

Trong code gốc mình chưa có dòng memset(a, 0, sizeof(a)); ở đầu init(). Khi kiểm tra lại mình phát hiện: nếu test trước có bản đồ lớn (ví dụ $6 \times 7$ toàn số $1$) và test sau nhỏ hơn (ví dụ $2 \times 2$), thì các ô cũ ở cột $n + 1$, hàng $m + 1$ vẫn còn giá trị $1$ – "viền núi lửa" không còn nữa và xe chạy lố ra ngoài bản đồ! Với ví dụ đó code cũ in ra $17$ thay vì $4$. Nên mình đã thêm dòng memset này vào cả 3 code trong bài. Bản Python tạo mảng mới cho mỗi test nên không bị lỗi này.

Các bạn bấm Tiếp để xem hàm Try đệ quy đi theo bậc thang ra sao. Ô vàng là ô $(i, j)$ đang xét, ô tím là các ô đã đi được với ô hạ cánh hiện tại (xanh lá):

C++▶ Chạy tay từng dòng codeCách 1: thử mọi ô hạ cánh, mỗi hướng gọi Try(dir, i, j) đi theo bậc thang (chưa có bảng nhớ).

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

Dữ liệu mẫu:

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

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6const int maxNM = 1005;

7int m, n;

8bool a[maxNM][maxNM];

9

10void init() {

11 memset(a, 0, sizeof(a));

12 cin >> m >> n;

13 string s;

14 for(int i = 1; i <= m; ++i) {

15 cin >> s;

16 for(int j = 0; j < n; ++j) {

17 a[i][j + 1] = (int)s[j] - 48;

18 }

19 }

20}

21

22// 0: up; 1: left; 2: right; 3: down.

23int Try(int dir, int i, int j) {

24 if(!a[i][j]) return 0;

25 if(dir == 0 && a[i][j + 1]) {

26 return Try(dir, i - 1, j + 1) + 2;

27 }

28 if(dir == 1 && a[i - 1][j]) {

29 return Try(dir, i - 1, j - 1) + 2;

30 }

31 if(dir == 2 && a[i + 1][j]) {

32 return Try(dir, i + 1, j + 1) + 2;

33 }

34 if(dir == 3 && a[i][j - 1]) {

35 return Try(dir, i + 1, j - 1) + 2;

36 }

37 return 1;

38}

39

40int solve() {

41 int res = 0;

42 for(int r0 = 1; r0 <= m; ++r0) {

43 for(int c0 = 1; c0 <= n; ++c0) {

44 if(a[r0][c0]) {

45 int sum = Try(0, r0 - 1, c0) + Try(1, r0, c0 - 1) + Try(2, r0, c0 + 1) + Try(3, r0 + 1, c0) + 1;

46 res = max(res, sum);

47 }

48 }

49 }

50 return res;

51}

52

53int main() {

54 ios_base::sync_with_stdio(0);

55 cin.tie(0);

56 int t;

57 cin >> t;

58 while(t--) {

59 init();

60 cout << solve() << endl;

61 }

62 return 0;

63}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(M \cdot N)$ cho bản đồ (cộng thêm độ sâu đệ quy, tối đa cỡ $\min(M, N)$ lời gọi).
• Thời gian: có $M \cdot N$ ô hạ cánh, mỗi ô đi 4 con đường bậc thang, mỗi con đường dài tới cỡ $2 \cdot \min(M, N)$ ô. Tổng cộng cỡ $O(M \cdot N \cdot \min(M, N))$ – với $M = N = 1000$ là khoảng $8 \cdot 10^9$ bước.

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

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

TLE ngay từ test 2

Nộp cách này lên Codeforces thì bị TLE ngay từ test 2. Mình đo thử: chỉ một bản đồ $1000 \times 1000$ toàn số $1$ thôi mà bản C++ đã chạy hơn 8 giây. Nhưng các bạn cứ nên cài đặt nó, vì chỉ cần "cải tiến thêm vài dòng" là thành cách AC ở ngay dưới đây.

Cách 2Đệ quy có nhớ (quy hoạch động top down) – O(M·N)

Để ý ở cách 1: hạ cánh tại ô $(4, 3)$ đi lên trên sẽ gọi Try(0, 3, 3), rồi Try(0, 2, 4)… Nhưng hạ cánh tại ô $(3, 4)$ đi lên trên cũng gọi đúng Try(0, 2, 4) – cả đoạn bậc thang phía sau lại bị đi lại từ đầu! Có rất nhiều lời gọi trùng nhau như vậy.

Ta cải tiến thành quy hoạch động top down – hay còn gọi là đệ quy có nhớ. Hàm Try(dir, i, j) có 3 biến đầu vào và cả 3 đều thay đổi khi gọi hàm, nên ta tạo một mảng 3 chiều f, với f[dir][i][j] lưu kết quả của Try(dir, i, j). Vì $dir \lt 4$; $i, j \lt maxNM$ nên khai báo int f[4][maxNM][maxNM];.

Mảng f phải là mảng toàn cục

Mảng f có $4 \cdot 1005 \cdot 1005 \approx 4 \cdot 10^6$ phần tử. Với mảng int có kích thước lớn hơn khoảng $2 \cdot 10^5$ thì anh em nên khai báo toàn cục (hoặc dùng vector), chứ khai báo trong hàm như bình thường sẽ bị tràn stack. Khai báo toàn cục còn có lợi là mọi phần tử tự động bằng $0$.

Khi gọi Try(dir, i, j): nếu đã từng tính rồi thì trả về f[dir][i][j] luôn; nếu chưa thì tính, gán vào f[dir][i][j] rồi trả về. Vậy làm sao biết "đã từng tính"? Mình đặt phần kiểm tra bảng nhớ sau điều kiện dừng. Qua được điều kiện dừng thì ô $(i, j)$ chắc chắn an toàn, nên số ô đi được ít nhất là $1$, tức f[dir][i][j] >= 1 nếu đã tính. Mà ban đầu mảng toàn cục toàn $0$, nên:

Dấu hiệu "đã tính"

f[dir][i][j] != 0 → đã tính, trả về luôn. f[dir][i][j] == 0 → chưa tính, phải đi tính rồi gán vào.

Thường thì các bạn sẽ thấy mình khởi tạo mảng nhớ toàn bộ bằng $-1$. Ở bài này làm vậy cũng được, nhưng sẽ tốn thêm thời gian gán $4 \cdot 10^6$ phần tử; nhận ra "$0$ = chưa tính" giúp code đỡ phải chạy hơn.

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

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const int maxNM = 1005;
int m, n;
bool a[maxNM][maxNM];

void init() {
    memset(a, 0, sizeof(a));
    cin >> m >> n;
    string s;
    for(int i = 1; i <= m; ++i) {
        cin >> s;
        for(int j = 0; j < n; ++j) {
            a[i][j + 1] = (int)s[j] - 48;
        }
    }
}

// 0: up; 1: left; 2: right; 3: down.
int f[4][maxNM][maxNM];
int Try(int dir, int i, int j) {
    if(!a[i][j]) {
        return 0;
    }
    if(f[dir][i][j]) {
        return f[dir][i][j];
    }
    if(dir == 0 && a[i][j + 1]) {
        return f[dir][i][j] = Try(dir, i - 1, j + 1) + 2;
    }
    if(dir == 1 && a[i - 1][j]) {
        return f[dir][i][j] = Try(dir, i - 1, j - 1) + 2;
    }
    if(dir == 2 && a[i + 1][j]) {
        return f[dir][i][j] = Try(dir, i + 1, j + 1) + 2;
    }
    if(dir == 3 && a[i][j - 1]) {
        return f[dir][i][j] = Try(dir, i + 1, j - 1) + 2;
    }
    return f[dir][i][j] = 1;
}

int solve() {
    int res = 0;
    for(int r0 = 1; r0 <= m; ++r0) {
        for(int c0 = 1; c0 <= n; ++c0) {
            if(a[r0][c0]) {
                int sum = Try(0, r0 - 1, c0) + Try(1, r0, c0 - 1) + Try(2, r0, c0 + 1) + Try(3, r0 + 1, c0) + 1;
                res = max(res, sum);
            }
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        memset(f, 0, sizeof(f));
        init();
        cout << solve() << endl;
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)


def Try(d, i, j):
    # 0: up; 1: left; 2: right; 3: down.
    if not a[i][j]:
        return 0
    if f[d][i][j]:
        return f[d][i][j]
    r = 1
    if d == 0 and a[i][j + 1]:
        r = Try(d, i - 1, j + 1) + 2
    elif d == 1 and a[i - 1][j]:
        r = Try(d, i - 1, j - 1) + 2
    elif d == 2 and a[i + 1][j]:
        r = Try(d, i + 1, j + 1) + 2
    elif d == 3 and a[i][j - 1]:
        r = Try(d, i + 1, j - 1) + 2
    f[d][i][j] = r
    return r


data = sys.stdin.read().split()
t = int(data[0])
p = 1
out = []
for _ in range(t):
    m, n = int(data[p]), int(data[p + 1])
    p += 2
    a = [[0] * (n + 2) for _ in range(m + 2)]
    for i in range(1, m + 1):
        s = data[p]
        p += 1
        for j in range(n):
            a[i][j + 1] = ord(s[j]) - 48
    f = [[[0] * (n + 2) for _ in range(m + 2)] for _ in range(4)]
    res = 0
    for r0 in range(1, m + 1):
        for c0 in range(1, n + 1):
            if a[r0][c0]:
                s = Try(0, r0 - 1, c0) + Try(1, r0, c0 - 1) + Try(2, r0, c0 + 1) + Try(3, r0 + 1, c0) + 1
                res = max(res, s)
    out.append(str(res))
print("\n".join(out))

Giải thích 1 số chỗ trong code:

1. return f[dir][i][j] = ...; nghĩa là gán f[dir][i][j] = ... xong rồi return f[dir][i][j].
2. Do có nhiều test nên trước mỗi test ta phải reset lại mảng f bằng memset(f, 0, sizeof(f)); – đưa toàn bộ phần tử về $0$. (Và như mình nói ở cách 1, bản đồ a cũng cần được xoá ở đầu init().)

Các bạn chạy thử ví dụ 2 và để ý những bước "đã tính rồi!" – đó chính là chỗ đệ quy có nhớ tiết kiệm thời gian so với cách 1:

C++▶ Chạy tay từng dòng codeCách 2: như cách 1 nhưng lưu Try(dir, i, j) vào f[dir][i][j], gặp lại thì trả về luôn.

Dữ liệu vào (stdin) – sửa thoải mái1 6 7 1101011 0111111 1111101 1111111 1111110 0111111

Dữ liệu mẫu:

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

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6const int maxNM = 1005;

7int m, n;

8bool a[maxNM][maxNM];

9

10void init() {

11 memset(a, 0, sizeof(a));

12 cin >> m >> n;

13 string s;

14 for(int i = 1; i <= m; ++i) {

15 cin >> s;

16 for(int j = 0; j < n; ++j) {

17 a[i][j + 1] = (int)s[j] - 48;

18 }

19 }

20}

21

22// 0: up; 1: left; 2: right; 3: down.

23int f[4][maxNM][maxNM];

24int Try(int dir, int i, int j) {

25 if(!a[i][j]) {

26 return 0;

27 }

28 if(f[dir][i][j]) {

29 return f[dir][i][j];

30 }

31 if(dir == 0 && a[i][j + 1]) {

32 return f[dir][i][j] = Try(dir, i - 1, j + 1) + 2;

33 }

34 if(dir == 1 && a[i - 1][j]) {

35 return f[dir][i][j] = Try(dir, i - 1, j - 1) + 2;

36 }

37 if(dir == 2 && a[i + 1][j]) {

38 return f[dir][i][j] = Try(dir, i + 1, j + 1) + 2;

39 }

40 if(dir == 3 && a[i][j - 1]) {

41 return f[dir][i][j] = Try(dir, i + 1, j - 1) + 2;

42 }

43 return f[dir][i][j] = 1;

44}

45

46int solve() {

47 int res = 0;

48 for(int r0 = 1; r0 <= m; ++r0) {

49 for(int c0 = 1; c0 <= n; ++c0) {

50 if(a[r0][c0]) {

51 int sum = Try(0, r0 - 1, c0) + Try(1, r0, c0 - 1) + Try(2, r0, c0 + 1) + Try(3, r0 + 1, c0) + 1;

52 res = max(res, sum);

53 }

54 }

55 }

56 return res;

57}

58

59int main() {

60 ios_base::sync_with_stdio(0);

61 cin.tie(0);

62 int t;

63 cin >> t;

64 while(t--) {

65 memset(f, 0, sizeof(f));

66 init();

67 cout << solve() << endl;

68 }

69 return 0;

70}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng f có $4 \cdot M \cdot N$ phần tử, mảng a có $M \cdot N$ phần tử, cộng lại là $O(5 \cdot M \cdot N)$.
• Thời gian: đọc đầu vào mất $M \cdot N$; còn hàm Try thì trường hợp xấu nhất cũng chỉ lấp đầy mảng f – mỗi trạng thái tính đúng 1 lần, mất thêm $4 \cdot M \cdot N$ phép tính. Tổng cộng $O(5 \cdot M \cdot N)$.

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

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

Với $M = N = 1000$ thì mất tầm $5 \cdot 10^6$ phép tính. Việc gọi đệ quy tốn thêm bộ nhớ và chút thời gian nữa nhưng không quá nhiều, nên hoàn toàn chạy kịp. Code trên đã AC bài này – ta chỉ cần code khéo phần vét cạn rồi cải tiến thêm vài dòng thành đệ quy có nhớ là xong 😎.

Độ sâu đệ quy có sợ tràn stack không?

Mỗi lần gọi đệ quy, con đường bậc thang tiến thêm 1 hàng và 1 cột, nên độ sâu đệ quy tối đa chỉ khoảng $\min(M, N) \le 1000$ – rất an toàn. Bản Python mình đặt sys.setrecursionlimit(10000) cho chắc.

Cách 3Quy hoạch động bottom up – đọc thêm

Cách trên là quy hoạch động top down, còn bây giờ mình làm theo kiểu bottom up: tạo ra công thức truy hồi và đi từ trường hợp cơ sở lên. Mỗi cách đều có ưu điểm riêng: top down thì chỉ cần sửa từ vét cạn là được; bottom up thì code dài hơn nhưng nhanh hơn vì không phải gọi đệ quy. Vẫn giữ quy ước hướng $0$: lên trên, $1$: sang trái, $2$: sang phải, $3$: xuống dưới. Cho ae nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước:

Bước 1 – Bài toán con: gọi F[dir][i][j] là số ô có thể đi được theo hướng dir bắt đầu từ ô $(i, j)$ ($0 \le dir \le 3$, $0 \le i, j \lt maxNM$). Mảng F[4][maxNM][maxNM] khai báo toàn cục.

Bước 2 – Bài toán cơ sở: nếu a[i][j] = 0 (núi lửa hoặc ngoài bản đồ) thì F[dir][i][j] = 0. Mảng toàn cục mặc định toàn $0$ nên khỏi làm gì.

Bước 3 – Đáp án: duyệt mọi ô an toàn $(r_0, c_0)$, tính sum = F[0][r0 - 1][c0] + F[1][r0][c0 - 1] + F[2][r0][c0 + 1] + F[3][r0 + 1][c0] + 1 rồi res = max(res, sum).

Bước 4 – Công thức truy hồi: chuyển thẳng từ phần xử lý chạy của hàm Try. Ví dụ với hướng lên trên: nếu a[i][j] != 0 thì mặc định F[0][i][j] = 1; nếu thêm a[i][j + 1] != 0 thì F[0][i][j] = F[0][i - 1][j + 1] + 2.

Công thức truy hồi (khi a[i][j] = 1)

• $F[0][i][j] = F[0][i-1][j+1] + 2$ nếu $a[i][j+1] = 1$, ngược lại $= 1$.
• $F[1][i][j] = F[1][i-1][j-1] + 2$ nếu $a[i-1][j] = 1$, ngược lại $= 1$.
• $F[2][i][j] = F[2][i+1][j+1] + 2$ nếu $a[i+1][j] = 1$, ngược lại $= 1$.
• $F[3][i][j] = F[3][i+1][j-1] + 2$ nếu $a[i][j-1] = 1$, ngược lại $= 1$.

Duyệt theo chiều nào?

Đây là điều quan trọng không kém: khi tính F[dir][i][j] thì ô nó phụ thuộc phải được tính trước rồi. Với hướng lên trên, công thức có $i - 1$ (i giảm) và $j + 1$ (j tăng), tức con đường đi về phía trên – phải. Để đi từ gốc lên (bottom up) thì ta duyệt ngược lại hướng đi: $i$ tăng dần và $j$ giảm dần. Khi đó mỗi lần cần tới [i - 1][j + 1] thì hàng $i - 1$ đã duyệt xong (vì $i$ đang tăng). Các ô ngoài bản đồ có cả a lẫn F bằng $0$ nên không phải lo.

Hướng	Công thức gọi tới	Vòng i	Vòng j
0 – lên trên	$[i-1][j+1]$	$1 \to m$ (tăng)	$n \to 1$ (giảm)
1 – sang trái	$[i-1][j-1]$	$1 \to m$ (tăng)	$1 \to n$ (tăng)
2 – sang phải	$[i+1][j+1]$	$m \to 1$ (giảm)	$n \to 1$ (giảm)
3 – xuống dưới	$[i+1][j-1]$	$m \to 1$ (giảm)	$1 \to n$ (tăng)

Các bạn chọn hướng rồi bấm Tiếp để xem bảng F[dir] được lấp dần theo đúng thứ tự duyệt. Ô cam là ô đang tính, ô viền xanh dương nét đứt là ô "bước 1" cần kiểm tra, ô viền xanh lá là ô mà công thức lấy giá trị – các bạn sẽ thấy nó luôn có giá trị sẵn rồi:

Bản đồ dir (0–3)

Ví dụ nhanh:

Gom 4 cụm vòng lặp trên vào một hàm go(), gọi ngay sau khi đọc xong bản đồ. Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const int maxNM = 1005;
int m, n;
bool a[maxNM][maxNM];
int f[4][maxNM][maxNM];

// 0: up; 1: left; 2: right; 3: down.
void go() {
    for(int i = 1; i <= m; ++i) {
        for(int j = n; j >= 1; --j) {
            if(a[i][j]) {
                f[0][i][j] = 1;
                if(a[i][j + 1]) {
                    f[0][i][j] = f[0][i - 1][j + 1] + 2;
                }
            }
        }
    }
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(a[i][j]) {
                f[1][i][j] = 1;
                if(a[i - 1][j]) {
                    f[1][i][j] = f[1][i - 1][j - 1] + 2;
                }
            }
        }
    }
    for(int i = m; i >= 1; --i) {
        for(int j = n; j >= 1; --j) {
            if(a[i][j]) {
                f[2][i][j] = 1;
                if(a[i + 1][j]) f[2][i][j] = f[2][i + 1][j + 1] + 2;
            }
        }
    }
    for(int i = m; i >= 1; --i) {
        for(int j = 1; j <= n; ++j) {
            if(a[i][j]) {
                f[3][i][j] = 1;
                if(a[i][j - 1]) {
                    f[3][i][j] = f[3][i + 1][j - 1] + 2;
                }
            }
        }
    }
}

void init() {
    memset(a, 0, sizeof(a));
    cin >> m >> n;
    string s;
    for(int i = 1; i <= m; ++i) {
        cin >> s;
        for(int j = 0; j < n; ++j) {
            a[i][j + 1] = (int)s[j] - 48;
        }
    }
    go();
}

int solve() {
    int res = 0;
    for(int r0 = 1; r0 <= m; ++r0) {
        for(int c0 = 1; c0 <= n; ++c0) {
            if(a[r0][c0]) {
                int sum = f[0][r0 - 1][c0] + f[1][r0][c0 - 1] + f[2][r0][c0 + 1] + f[3][r0 + 1][c0] + 1;
                res = max(res, sum);
            }
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        memset(f, 0, sizeof(f));
        init();
        cout << solve() << endl;
    }
    return 0;
}

import sys


def go(m, n, a):
    # 0: up; 1: left; 2: right; 3: down.
    f = [[[0] * (n + 2) for _ in range(m + 2)] for _ in range(4)]
    f0, f1, f2, f3 = f
    for i in range(1, m + 1):
        for j in range(n, 0, -1):
            if a[i][j]:
                f0[i][j] = f0[i - 1][j + 1] + 2 if a[i][j + 1] else 1
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i][j]:
                f1[i][j] = f1[i - 1][j - 1] + 2 if a[i - 1][j] else 1
    for i in range(m, 0, -1):
        for j in range(n, 0, -1):
            if a[i][j]:
                f2[i][j] = f2[i + 1][j + 1] + 2 if a[i + 1][j] else 1
    for i in range(m, 0, -1):
        for j in range(1, n + 1):
            if a[i][j]:
                f3[i][j] = f3[i + 1][j - 1] + 2 if a[i][j - 1] else 1
    return f


data = sys.stdin.read().split()
t = int(data[0])
p = 1
out = []
for _ in range(t):
    m, n = int(data[p]), int(data[p + 1])
    p += 2
    a = [[0] * (n + 2) for _ in range(m + 2)]
    for i in range(1, m + 1):
        s = data[p]
        p += 1
        for j in range(n):
            a[i][j + 1] = ord(s[j]) - 48
    f0, f1, f2, f3 = go(m, n, a)
    res = 0
    for r0 in range(1, m + 1):
        for c0 in range(1, n + 1):
            if a[r0][c0]:
                s = f0[r0 - 1][c0] + f1[r0][c0 - 1] + f2[r0][c0 + 1] + f3[r0 + 1][c0] + 1
                res = max(res, s)
    out.append(str(res))
print("\n".join(out))

C++▶ Chạy tay từng dòng codeCách 3: lấp 4 bảng f[0..3] bằng 4 cụm vòng lặp (đúng chiều duyệt), rồi cộng 4 hướng cho mỗi ô.

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

Dữ liệu mẫu:

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

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6const int maxNM = 1005;

7int m, n;

8bool a[maxNM][maxNM];

9int f[4][maxNM][maxNM];

10

11// 0: up; 1: left; 2: right; 3: down.

12void go() {

13 for(int i = 1; i <= m; ++i) {

14 for(int j = n; j >= 1; --j) {

15 if(a[i][j]) {

16 f[0][i][j] = 1;

17 if(a[i][j + 1]) {

18 f[0][i][j] = f[0][i - 1][j + 1] + 2;

19 }

20 }

21 }

22 }

23 for(int i = 1; i <= m; ++i) {

24 for(int j = 1; j <= n; ++j) {

25 if(a[i][j]) {

26 f[1][i][j] = 1;

27 if(a[i - 1][j]) {

28 f[1][i][j] = f[1][i - 1][j - 1] + 2;

29 }

30 }

31 }

32 }

33 for(int i = m; i >= 1; --i) {

34 for(int j = n; j >= 1; --j) {

35 if(a[i][j]) {

36 f[2][i][j] = 1;

37 if(a[i + 1][j]) f[2][i][j] = f[2][i + 1][j + 1] + 2;

38 }

39 }

40 }

41 for(int i = m; i >= 1; --i) {

42 for(int j = 1; j <= n; ++j) {

43 if(a[i][j]) {

44 f[3][i][j] = 1;

45 if(a[i][j - 1]) {

46 f[3][i][j] = f[3][i + 1][j - 1] + 2;

47 }

48 }

49 }

50 }

51}

52

53void init() {

54 memset(a, 0, sizeof(a));

55 cin >> m >> n;

56 string s;

57 for(int i = 1; i <= m; ++i) {

58 cin >> s;

59 for(int j = 0; j < n; ++j) {

60 a[i][j + 1] = (int)s[j] - 48;

61 }

62 }

63 go();

64}

65

66int solve() {

67 int res = 0;

68 for(int r0 = 1; r0 <= m; ++r0) {

69 for(int c0 = 1; c0 <= n; ++c0) {

70 if(a[r0][c0]) {

71 int sum = f[0][r0 - 1][c0] + f[1][r0][c0 - 1] + f[2][r0][c0 + 1] + f[3][r0 + 1][c0] + 1;

72 res = max(res, sum);

73 }

74 }

75 }

76 return res;

77}

78

79int main() {

80 ios_base::sync_with_stdio(0);

81 cin.tie(0);

82 int t;

83 cin >> t;

84 while(t--) {

85 memset(f, 0, sizeof(f));

86 init();

87 cout << solve() << endl;

88 }

89 return 0;

90}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: như cách top down, $O(5 \cdot M \cdot N)$.
• Thời gian: đọc mảng a và lấp đầy cả 4 bảng f: $O(5 \cdot M \cdot N)$. Độ phức tạp giống cách top down nhưng thực tế bottom up tiết kiệm thời gian và bộ nhớ hơn một chút vì không tốn cho việc gọi đệ quy.

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

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

Cách này dài dòng hơn cách top down. Nhưng các bạn cứ thấy cách nào dễ hiểu và dễ thực hiện thì làm thôi, tuỳ vào cả giới hạn dữ liệu của bài nữa.

Bạn nào code Python để ý

Bản Python của cách 2 và cách 3 cho kết quả đúng, nhưng Python chậm hơn C++ nhiều: mình đo với một bản đồ $1000 \times 1000$ toàn số $1$, cách 2 (đệ quy có nhớ) mất khoảng 7.6 giây, cách 3 (bottom up) khoảng 3.3 giây – mà trên Codeforces một file có tới 20 bản đồ. Nên bài này các bạn nên nộp bằng C++.

Ghi chú của mình: cả 3 code C++ và 3 code Python ở trên đều cho đúng output 2 ví dụ của đề, và đã được so với một code mô phỏng trực tiếp (cho xe tự hành chạy từng bước quẹo phải/quẹo trái, đếm các ô khác nhau) trên 500 file test ngẫu nhiên, mỗi file 1–5 bản đồ kích thước tới $9 \times 9$ – khớp hết. Với file 20 bản đồ $1000 \times 1000$: cách 2 (C++) chạy khoảng 1.6 giây, cách 3 (C++) khoảng 0.8 giây; còn cách 1 chỉ với 1 bản đồ $1000 \times 1000$ toàn số $1$ đã mất hơn 8 giây.

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 😇