Số Cách Đi Quân Mã (SOCACH) (Olympic 30/4 2023 – Tin học khối 10)
Đề bài
Câu 1. (6 điểm) Số cách đi quân mã
Xét một bàn cờ vua có kích thước $m \times n$ gồm có $m$ dòng, $n$ cột. Các dòng được đánh số từ $1$ đến $m$, các cột được đánh số từ $1$ đến $n$. Một ô nằm trên dòng $x$, cột $y$ được kí hiệu là $(x, y)$.
Một quân mã xuất phát từ một ô trên bàn cờ có thể đi đến một trong bốn ô như hình vẽ.
Ngoài ra, trên bàn cờ có $k$ ô mà quân mã không được phép đi vào. Những ô này được gọi là ô bị cấm.
Yêu cầu: Tìm số cách di chuyển của quân mã từ ô $(x, y)$ cho trước đến ô $(m, n)$.
Dữ liệu vào: Cho trong file văn bản SOCACH.INP gồm:
- Dòng đầu tiên ghi 4 số nguyên $m, n, k$ và $Q$ $(1 \lt m, n \le 1000;\ 0 \le k \le 10;\ Q \le 10^5)$.
- Trên $k$ dòng tiếp theo, mỗi dòng ghi 2 số nguyên $kx_i, ky_i$ cho biết ô $(kx_i, ky_i)$ bị cấm $(1 \le kx_i \lt m;\ 1 \le ky_i \lt n)$.
- Trên $Q$ dòng tiếp theo, mỗi dòng ghi 2 số nguyên $x_i, y_i$ $(1 \le x_i \lt m;\ 1 \le y_i \lt n)$.
Các số trên một dòng cách nhau bởi ít nhất một khoảng trắng.
Kết quả: Đưa ra file văn bản SOCACH.OUT, gồm $Q$ số nguyên $W_i$, mỗi số trên một dòng cho biết cách di chuyển quân mã từ ô $(x_i, y_i)$ cho trước đến ô $(m, n)$. Trong đó $W_i$ là phần dư của phép chia số cách quân mã di chuyển từ ô $(x_i, y_i)$ cho trước đến ô $(m, n)$ cho $10^9$.
Ràng buộc:
- 30% test ứng với 30% số điểm của bài có $1 \lt m, n \le 100;\ k = 0;\ Q \le 10^2$.
- 20% test ứng với 20% số điểm của bài có $1 \lt m, n \le 100;\ 0 \lt k \le 10;\ Q \le 10^2$.
- 50% test ứng với 50% số điểm của bài có ràng buộc như đề bài.
Thời gian làm bài cả đề: 180 phút. Đề gốc đọc/ghi file SOCACH.INP / SOCACH.OUT; code trong bài này đọc từ bàn phím và in ra màn hình cho dễ chạy thử, đi thi thì các bạn thêm 2 dòng freopen("SOCACH.INP", "r", stdin); freopen("SOCACH.OUT", "w", stdout); ở đầu hàm main nhé.
4 5 1 3
2 4
1 2
3 3
2 41
1
04 5 0 2
1 2
3 32
1Lời mở đầu
Bài này nằm trong đề thi Olympic truyền thống 30 tháng 4 lần thứ XXVII năm 2023, môn Tin học khối 10. Mình viết hướng dẫn giải theo cách làm của mình để các bạn tham khảo thử. 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é:
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 OJTrước tiên mình vẽ lại cho rõ 4 nước đi của quân mã. Đứng ở ô $(x, y)$, quân mã chỉ được đi tới:
dx = {-1, 1, 2, 2}, dy = {2, 2, 1, -1}.Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ:
- Ví dụ 1: bàn cờ 4 dòng, 5 cột, ô $(2, 4)$ bị cấm, đích là $(4, 5)$.
- Từ $(1, 2)$: nước ① ra ngoài bàn cờ; nước ② tới $(2, 4)$ bị cấm; nước ③ tới $(3, 3)$, từ đó nước ② nhảy thẳng tới $(4, 5)$ ✔; nước ④ tới $(3, 1)$ thì đi vòng kiểu gì cũng bị kẹt, không tới được $(4, 5)$. Vậy chỉ có 1 cách: $(1,2) \to (3,3) \to (4,5)$.
- Từ $(3, 3)$: đúng 1 cách $(3,3) \to (4,5)$.
- Ô $(2, 4)$ bị cấm, quân mã không được đứng ở đó nên đáp án là 0.
- Ví dụ 2: không có ô cấm, nên từ $(1, 2)$ có thêm đường $(1,2) \to (2,4) \to (4,5)$, tổng cộng 2 cách; từ $(3, 3)$ vẫn là 1 cách.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Đồ thị DAG + thứ tự topo + quy hoạch động – O(m·n + Q)
Do đó, nếu ta xem mỗi ô trên bàn cờ là một đỉnh của đồ thị, ta sẽ có $m \cdot n$ đỉnh. Đỉnh $(i, j)$ nối tới $(i', j')$ nếu quân mã nhảy được từ $(i, j)$ sang $(i', j')$ (và cả 2 ô đều không bị cấm). Vì con mã không thể nhảy về lại vị trí đã nhảy, đồ thị này là một đồ thị có hướng không chu trình – DAG. Trên DAG thì việc đếm số đường đi là "đất diễn" quen thuộc của quy hoạch động.
Để có thể dùng quy hoạch động, ta cần sắp xếp các đỉnh theo thứ tự topo, để bảo đảm rằng đỉnh nào xuất hiện trước trong thứ tự topo thì đỉnh đó sẽ có đáp án bài toán trước (đã nhận đủ "số cách" từ mọi đỉnh dẫn tới nó rồi mới đem đi cộng tiếp).
- Gọi $dp[\{x, y\}]$ là số cách để mã nhảy (theo chiều ngược) từ ô $(m, n)$ đến đỉnh $(x, y)$ – cũng chính là số cách đi xuôi từ $(x, y)$ tới $(m, n)$.
- Bài toán cơ sở: $dp[\{m, n\}] = 1$.
- Duyệt các đỉnh theo thứ tự topo. Khi đỉnh $\{x, y\}$ hiện tại có $dp[\{x, y\}] \gt 0$, ta xét các đỉnh $\{x', y'\}$ kề với nó (trong đồ thị ngược) và cập nhật $dp[\{x', y'\}] \mathrel{+}= dp[\{x, y\}]$ (lấy dư cho $10^9$).
- Với mỗi truy vấn $\{x, y\}$, ta xuất $dp[\{x, y\}]$.
Để thuận lợi cho việc tính quy hoạch động, ta đánh số các đỉnh $(x, y)$ thành một số nguyên duy nhất theo chiều từ trên xuống dưới và từ trái sang phải. Trong code, mình dùng chỉ số dòng/cột từ $0$ và đổi bằng hàm calc(x, y) = m * x + y; chiều ngược lại là convertToCoordinate(u) = (u / m, u % m).
n là số dòng và m là số cột (đọc cin >> n >> m >> k >> q), ngược tên so với đề nhưng thứ tự đọc vẫn đúng. Các bạn đọc code để ý chỗ này kẻo rối nha.Các bước cụ thể của chương trình:
- Dựng đồ thị ngược: với mỗi ô $(x, y)$ không bị cấm, thử 4 nước đi tới $(xx, yy)$; nếu $(xx, yy)$ nằm trong bàn cờ và không bị cấm thì thêm cạnh
adj[calc(xx, yy)].push_back(calc(x, y))– tức là cạnh đi ngược từ ô đến về ô đi. - Tìm thứ tự topo bằng DFS: chạy
dfstrên đồ thị ngược, đỉnh nào duyệt xong toàn bộ các đỉnh con thì đẩy vào stackstore. Lấy lần lượt từ đỉnh stack ra ta được thứ tự topo. Mảngblockedvừa dùng để đánh dấu ô cấm, vừa dùng luôn làm mảng "đã thăm" của DFS – ô cấm coi như đã thăm sẵn nên không bao giờ được đi vào. - Quy hoạch động theo thứ tự topo:
dp[calc(n - 1, m - 1)] = 1, rồi đi theo thứ tự topo, đỉnh nào códp > 0thì cộngdpcủa nó sang các đỉnh kề. - Trả lời truy vấn trong $O(1)$.
Source code theo tư tưởng mình đã trình bày ở trên:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000000;
int dx[4] = {-1, 1, 2, 2};
int dy[4] = {2, 2, 1, -1};
int n, m, k, q;
stack <int> store;
vector <int> topo;
int dp[1000005];
bool blocked[1005][1005];
vector <int> adj[1000005];
int calc(int x, int y) {
return m * x + y;
}
pair <int, int> convertToCoordinate(int value) {
return make_pair(value / m, value % m);
}
void dfs(int u) {
pair <int, int> currentCoordinate = convertToCoordinate(u);
blocked[currentCoordinate.first][currentCoordinate.second] = true;
for (int i = 0; i < (int) adj[u].size(); i++) {
int v = adj[u][i];
pair <int, int> coor = convertToCoordinate(v);
if (blocked[coor.first][coor.second] == false) {
dfs(v);
}
}
store.push(u);
}
int main () {
cin >> n >> m >> k >> q;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
blocked[x - 1][y - 1] = true;
}
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (blocked[x][y] == true) {
continue;
}
for (int t = 0; t < 4; t++) {
int xx = x + dx[t];
int yy = y + dy[t];
if (xx >= 0 && xx < n && yy >= 0 && yy < m && blocked[xx][yy] == false) {
adj[calc(xx, yy)].push_back(calc(x, y));
}
}
}
}
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (blocked[x][y] == false) {
dfs(calc(x, y));
}
}
}
while (store.empty() == false) {
topo.push_back(store.top());
store.pop();
}
dp[calc(n - 1, m - 1)] = 1;
for (int i = 0; i < (int) topo.size(); i++) {
if (dp[topo[i]] > 0) {
int u = topo[i];
for (int j = 0; j < (int) adj[u].size(); j++) {
int v = adj[u][j];
(dp[v] += dp[u]) %= mod;
}
}
}
for (int query = 0; query < q; query++) {
int x, y;
cin >> x >> y;
cout << dp[calc(x - 1, y - 1)] << endl;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, k, q = int(data[0]), int(data[1]), int(data[2]), int(data[3])
mod = 1000000000
dx = [-1, 1, 2, 2]
dy = [2, 2, 1, -1]
blocked = [False] * (n * m) # đỉnh (x, y) được đánh số x * m + y
p = 4
for _ in range(k):
x, y = int(data[p]) - 1, int(data[p + 1]) - 1; p += 2
blocked[x * m + y] = True
adj = [[] for _ in range(n * m)]
for x in range(n):
for y in range(m):
if blocked[x * m + y]:
continue
for t in range(4):
xx = x + dx[t]; yy = y + dy[t]
if 0 <= xx < n and 0 <= yy < m and not blocked[xx * m + yy]:
adj[xx * m + yy].append(x * m + y)
# DFS (dùng stack tự quản lý thay cho đệ quy) để lấy thứ tự topo
store = []
for s in range(n * m):
if blocked[s]:
continue
blocked[s] = True
st = [(s, 0)]
while st:
u, i = st[-1]
if i < len(adj[u]):
st[-1] = (u, i + 1)
v = adj[u][i]
if not blocked[v]:
blocked[v] = True
st.append((v, 0))
else:
st.pop()
store.append(u)
topo = store[::-1]
dp = [0] * (n * m)
dp[(n - 1) * m + (m - 1)] = 1
for u in topo:
if dp[u] > 0:
for v in adj[u]:
dp[v] = (dp[v] + dp[u]) % mod
out = []
for _ in range(q):
x, y = int(data[p]) - 1, int(data[p + 1]) - 1; p += 2
out.append(dp[x * m + y])
print("\n".join(map(str, out)))
main()Bản Python mình viết DFS bằng stack tự quản lý thay cho đệ quy (Python giới hạn độ sâu đệ quy và gọi hàm khá chậm), còn ý tưởng giữ nguyên như bản C++.
Các bạn bấm Tiếp ▶ để chạy tay từng dòng code C++ ở trên. Bảng bên dưới vẽ bàn cờ theo chỉ số từ 0 như trong code: lúc dựng đồ thị mỗi ô hiện số hiệu đỉnh calc(x, y), đến phần quy hoạch động thì mỗi ô hiện giá trị dp. Ô đen là ô cấm, ô xanh tím là ô DFS đã thăm.
Đánh giá độ phức tạp của cách làm này:
- Không gian: đồ thị có $m \cdot n \le 10^6$ đỉnh, mỗi đỉnh tối đa 4 cạnh, cộng thêm mảng
dp, stack và mảngtopo⇒ $O(m \cdot n)$. Do dùngvector<int> adj[1000005]nên bộ nhớ khá "nặng" (mình đo được khoảng 70 MB khi $m = n = 1000$). - Thời gian: dựng đồ thị, DFS và QHĐ đều duyệt mỗi đỉnh, mỗi cạnh một lần ⇒ $O(m \cdot n)$; mỗi truy vấn $O(1)$ ⇒ tổng $O(m \cdot n + Q)$.
dp luôn nhỏ hơn $10^9$, cộng 2 số thì vẫn dưới $2 \cdot 10^9 \lt 2^{31} - 1$ nên dùng int không bị tràn.Cách 2Quy hoạch động theo đường chéo x + y – O(m·n + Q)
Cách 1 đã giải quyết trọn vẹn bài toán. Phần này mình bổ sung thêm một góc nhìn để code gọn hơn: nếu ta tìm được sẵn một thứ tự topo "cho không" thì khỏi cần dựng đồ thị và chạy DFS.
Gọi $dp[x][y]$ là số cách đi từ ô $(x, y)$ tới ô $(m, n)$. Khi đó:
$dp[x][y] = dp[x-1][y+2] + dp[x+1][y+2] + dp[x+2][y+1] + dp[x+2][y-1]$
(ô nào ra ngoài bàn cờ thì coi như bằng $0$, kết quả lấy dư cho $10^9$).
Cả 4 ô ở vế phải đều có tổng toạ độ lớn hơn $x + y$. Vậy ta chỉ cần tính các ô theo thứ tự $x + y$ giảm dần: đi từng đường chéo phụ $s = x + y$ từ $m + n - 1$ xuống $2$. Khi tới ô $(x, y)$ thì 4 ô nó cần đã được tính xong hết rồi.
Minh hoạ tính dp theo từng đường chéo
Em nhập kích thước bàn cờ và các ô cấm rồi bấm Tiếp. Ô vàng là ô đang tính, các ô tím là những ô nó lấy giá trị cộng lại, viền cam là đường chéo $x + y$ đang xét:
Source code để các bạn tham khảo nếu làm theo hướng này (ở đây mình đặt tên biến đúng như đề: m là số dòng, n là số cột):
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000;
int dp[1005][1005];
bool cam[1005][1005];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int m, n, k, q;
cin >> m >> n >> k >> q;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
cam[x][y] = true;
}
dp[m][n] = 1;
for (int s = m + n - 1; s >= 2; s--) {
for (int x = max(1, s - n); x <= min(m, s - 1); x++) {
int y = s - x;
if (cam[x][y]) continue;
long long t = 0;
if (x - 1 >= 1 && y + 2 <= n) t += dp[x - 1][y + 2];
if (x + 1 <= m && y + 2 <= n) t += dp[x + 1][y + 2];
if (x + 2 <= m && y + 1 <= n) t += dp[x + 2][y + 1];
if (x + 2 <= m && y - 1 >= 1) t += dp[x + 2][y - 1];
dp[x][y] = t % MOD;
}
}
while (q--) {
int x, y;
cin >> x >> y;
cout << dp[x][y] << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
m, n, k, q = int(data[0]), int(data[1]), int(data[2]), int(data[3])
MOD = 10**9
cam = [[False] * (n + 3) for _ in range(m + 3)]
p = 4
for _ in range(k):
x, y = int(data[p]), int(data[p + 1]); p += 2
cam[x][y] = True
# dp có viền 0 bao quanh: hàng 0, hàng m+1, m+2; cột 0, n+1, n+2
dp = [[0] * (n + 3) for _ in range(m + 3)]
dp[m][n] = 1
for s in range(m + n - 1, 1, -1):
for x in range(max(1, s - n), min(m, s - 1) + 1):
y = s - x
if cam[x][y]:
continue
a = dp[x + 1]; b = dp[x + 2]
dp[x][y] = (dp[x - 1][y + 2] + a[y + 2] + b[y + 1] + b[y - 1]) % MOD
out = []
for _ in range(q):
x, y = int(data[p]), int(data[p + 1]); p += 2
out.append(dp[x][y])
print("\n".join(map(str, out)))
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ cần mảng
dpvà mảngcamkích thước $m \times n$ ⇒ $O(m \cdot n)$, khoảng 5 MB. - Thời gian: mỗi ô tính đúng 1 lần với 4 phép cộng ⇒ $O(m \cdot n)$, mỗi truy vấn $O(1)$ ⇒ $O(m \cdot n + Q)$.
- 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.
- 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.
Nhận xét
Đăng nhận xét