Quay lui (2)
- Độ khó
- ★★★★★ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Quay lui (1), Mảng 2 chiều
- Chủ đề
- mảng 2 chiềuquay lui
- Trạng thái
Kiến thức cơ bản
Nhắc lại khuôn quay lui
Tuần trước, em đã học khuôn quay lui: điều kiện dừng, thử từng lựa chọn hợp lệ, đi tiếp rồi hủy lựa chọn. Tuần này, ta dùng khuôn đó cho bốn kiểu bài mới: đi trên lưới, loang, đặt quân hậu, và những bài chỉ cần tìm một nghiệm hoặc nghiệm tốt nhất. Hãy nhớ mỗi lần “hủy lựa chọn”, em phải trả lại mọi thứ đúng như cũ (xóa dấu chân).
Mẫu 1: Đi trên lưới
Thỏ đứng ở góc trên trái của một mê cung n × m, muốn đến góc dưới phải. Ô '.' đi được, ô '#' là tường. Mỗi bước Thỏ đi sang một ô kề nhau (lên, xuống, trái, phải) và không đi lại ô đã đi qua trong cùng một đường. Hỏi có bao nhiêu đường đi khác nhau?
Ta dùng hai mảng dx, dy để viết bốn hướng thật gọn: hướng d đi từ (x, y) sang (x + dx[d], y + dy[d]). Mảng vis đánh dấu các ô đang nằm trên đường đi hiện tại.
Lưới 3 x 3: Bốn hướng d: 0 lên (dx, dy) = (-1, 0)
S . . 1 xuống (dx, dy) = ( 1, 0)
. # . 2 trái (dx, dy) = ( 0, -1)
. . E 3 phải (dx, dy) = ( 0, 1)
int n, m, dem = 0;
char g[10][10]; // '.' là ô đi được, '#' là tường
bool vis[10][10]; // vis = true nếu ô đang nằm trên đường đi hiện tại
int dx[4] = {-1, 1, 0, 0}; // bốn hướng: lên, xuống, trái, phải
int dy[4] = {0, 0, -1, 1};
void Try(int x, int y) {
if (x == n - 1 && y == m - 1) { // đến đích: được thêm một đường đi
dem++;
return;
}
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // ra ngoài bảng
if (g[nx][ny] == '#' || vis[nx][ny]) continue; // tường hoặc đã đi qua
vis[nx][ny] = true; // bước vào ô mới
Try(nx, ny);
vis[nx][ny] = false; // quay lui: xóa dấu để đường khác còn dùng được ô này
}
}
// trong main: vis[0][0] = true; Try(0, 0);
Dòng vis[nx][ny] = false rất quan trọng. Nếu quên, các đường đi sau không dùng được ô này nữa và kết quả đếm bị thiếu.
Mẫu 2: Loang, đếm vùng (không cần quay lui)
Bài toán: bản đồ gồm các ô '.' (đất) và '#' (nước). Hỏi có bao nhiêu mảnh đất, hai ô đất thuộc cùng một mảnh nếu đi từ ô này sang ô kia bằng các bước lên, xuống, trái, phải qua các ô đất? Ta duyệt từng ô; gặp ô đất chưa thăm thì tăng số mảnh và loang ra mọi ô đất cùng mảnh. Khi loang, em chỉ cần biết ô đã được thăm hay chưa, nên đánh dấu rồi không xóa (khác với đếm đường đi). Mỗi ô được thăm đúng một lần nên cả bài chỉ tốn khoảng n × m bước.
void Loang(int x, int y) { // đánh dấu cả vùng chứa ô (x, y)
vis[x][y] = true; // đánh dấu và KHÔNG xóa
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (g[nx][ny] == '#' || vis[nx][ny]) continue;
Loang(nx, ny);
}
}
// đếm vùng:
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '.' && !vis[i][j]) { vung++; Loang(i, j); }
Mẫu 3: N quân hậu
Quân hậu trong cờ vua chiếu theo hàng, cột và hai đường chéo. Hãy đặt n quân hậu lên bàn cờ n × n sao cho không có hai quân nào chiếu nhau. Vì mỗi hàng chỉ có một quân, ta đặt lần lượt từng hàng. Với mỗi hàng, thử từng cột còn trống. Để kiểm tra nhanh, ta nhớ ba loại đường đã bị chiếm: cột c, đường chéo xuôi (có hàng + cột không đổi) và đường chéo ngược (có hàng - cột không đổi).
n = 4, một cách đặt (Q là quân hậu):
. Q . . hàng 0, cột 1
. . . Q hàng 1, cột 3
Q . . . hàng 2, cột 0
. . Q . hàng 3, cột 2
n = 4 chỉ có đúng 2 cách đặt, n = 8 có 92 cách.
int n, dem = 0;
bool col[20], d1[40], d2[40]; // cột, chéo xuôi (hàng + cột), chéo ngược (hàng - cột + n)
void Try(int r) { // đặt quân hậu ở hàng r
if (r == n) { dem++; return; }
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c + n]) continue; // bị quân khác chiếu
col[c] = d1[r + c] = d2[r - c + n] = true; // đặt quân
Try(r + 1);
col[c] = d1[r + c] = d2[r - c + n] = false; // quay lui: nhấc quân
}
}
Mẫu 4: Dừng sớm khi chỉ cần một nghiệm
Có những bài chỉ hỏi “có cách nào không?” hoặc “hãy in một cách”. Khi đã tìm thấy, ta không cần thử tiếp. Cho hàm Try trả về bool: true nghĩa là đã tìm thấy, và mọi hàm Try bên ngoài thấy true thì lập tức trả true về trên. Cách này tiết kiệm rất nhiều thời gian khi nghiệm xuất hiện sớm.
bool Try(int i, long long sum) { // trả về true nếu đã tìm được cách chọn
if (sum == target) return true;
if (i == n || sum > target) return false;
if (Try(i + 1, sum + a[i])) return true; // tìm thấy ở nhánh này: dừng ngay, không thử nhánh khác
return Try(i + 1, sum);
}
Mẫu 5: Tìm nghiệm tốt nhất
Với bài hỏi giá trị nhỏ nhất (hoặc lớn nhất) của mọi cách, em dùng một biến best ghi giá trị tốt nhất đã gặp. Ở điều kiện dừng thì cập nhật best. Em cắt tỉa khi phần đã đi chắc chắn không thể tốt hơn best (ví dụ chi phí đã đi không nhỏ hơn best khi tìm giá trị nhỏ nhất và chi phí chỉ tăng). Đừng quên khởi tạo best là một giá trị rất lớn (hoặc rất nhỏ).
Nhận dạng đề bài
| Dấu hiệu trong đề | Cách làm | Điều cần chú ý |
|---|---|---|
| Đếm số vùng, diện tích vùng, có đường đi hay không | Loang (đệ quy trên lưới), vis đánh dấu rồi không xóa | Mỗi ô chỉ cần thăm một lần |
| Đếm mọi đường đi, tìm đường đi qua nhiều ô | Quay lui trên lưới, vis đánh dấu rồi xóa khi quay lui | Mỗi đường đi có thể đi qua cùng một ô |
| Đặt các quân sao cho không chiếu nhau | Quay lui theo hàng, mảng col, d1, d2 | Chọn đặt quân theo từng hàng một |
| Chỉ cần biết có hay không (YES/NO) hoặc một nghiệm | Hàm Try trả về bool, true thì dừng | Dừng ngay khi tìm thấy |
| Tìm giá trị nhỏ nhất, lớn nhất trong mọi cách | Biến best, cắt tỉa khi đã không thể tốt hơn | Cập nhật best ở điều kiện dừng |
Luyện tập
Bài 1. Có đường ra không
Thỏ bị lạc trong một khu rừng n × m ô. Ô '.' là lối đi, ô '#' là cây to chắn đường. Thỏ đang ở ô góc trên trái (hàng 1, cột 1) và muốn ra khỏi rừng ở ô góc dưới phải (hàng n, cột m). Mỗi bước, Thỏ đi sang một ô kề cạnh (lên, xuống, trái, phải) không phải cây. Thỏ có ra được không? Dữ liệu đảm bảo hai ô đó đều là '.'.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | In YES nếu Thỏ ra được, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 3 3 ..# #.. #.. | YES |
| 2 | 3 3 .#. #.. ... | NO |
Bài 2. Đếm đảo
Bản đồ của Gấu Po là một lưới n × m. Ô '#' là đất liền, ô '.' là biển. Các ô đất kề nhau theo cạnh (trên, dưới, trái, phải) tạo thành cùng một hòn đảo. Hỏi bản đồ có bao nhiêu hòn đảo?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | Số hòn đảo. | |
| Test | Input | Output |
| 1 | 4 5 ##..# #...# ..#.. #.### | 4 |
| 2 | 2 2 .. .. | 0 |
Bài 3. Hòn đảo lớn nhất
Với bản đồ như bài trước, Hổ muốn biết hòn đảo lớn nhất có bao nhiêu ô đất.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | Số ô của hòn đảo lớn nhất (in 0 nếu không có đất). | |
| Test | Input | Output |
| 1 | 4 5 ##..# #...# ..#.. #.### | 4 |
| 2 | 2 2 .. .. | 0 |
Bài 4. Đếm đường đi trong mê cung
Gấu Po ở ô góc trên trái của một mê cung n × m, muốn đến ô góc dưới phải. Ô '.' đi được, ô '#' là tường. Mỗi bước, Gấu Po đi sang một ô kề cạnh và không đi lại ô nào đã đi qua trong cùng một đường. Hỏi có bao nhiêu đường đi khác nhau?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 5). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | Số đường đi khác nhau. Dữ liệu đảm bảo hai ô xuất phát và đích đều là '.'. | |
| Test | Input | Output |
| 1 | 3 3 ... ... ... | 12 |
| 2 | 3 3 .#. ... ... | 4 |
Bài 5. Đường đi ngắn nhất trong mê cung
Thỏ ở ô góc trên trái của một mê cung n × m, muốn đến ô góc dưới phải. Ô '.' đi được, ô '#' là tường. Mỗi bước Thỏ đi sang một ô kề cạnh. Hỏi số bước ít nhất để đến đích? Hãy giải bằng quay lui và cắt tỉa khi số bước đã đi không nhỏ hơn đáp án tốt nhất.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 6). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | Số bước ít nhất, hoặc -1 nếu không đến được. Dữ liệu đảm bảo hai ô xuất phát và đích đều là '.'. | |
| Test | Input | Output |
| 1 | 3 3 ... ... ... | 4 |
| 2 | 3 3 .#. ### ... | -1 |
Bài 6. Chia kẹo đều
Hổ có n gói kẹo, gói thứ i có a[i] viên. Hổ muốn chia các gói thành hai phần có tổng số viên bằng nhau (mỗi gói thuộc đúng một phần, không được chia nhỏ gói). Có làm được không? Hãy dừng ngay khi tìm thấy cách chia.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 20). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | In YES nếu chia được, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 4 1 5 11 5 | YES |
| 2 | 3 1 2 4 | NO |
Bài 7. Đếm cách đặt hậu
Gấu Po muốn đặt n quân hậu lên bàn cờ n × n sao cho không có hai quân nào chiếu nhau (cùng hàng, cùng cột hoặc cùng đường chéo). Hỏi có bao nhiêu cách đặt?
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 9). | |
|---|---|---|
| Đầu ra | Số cách đặt. | |
| Test | Input | Output |
| 1 | 4 | 2 |
| 2 | 6 | 4 |
Bài 8. Một cách đặt hậu
Thỏ muốn đặt n quân hậu lên bàn cờ n × n sao cho không có hai quân nào chiếu nhau. Hãy in cách đặt đầu tiên theo thứ tự từ điển, tức là dãy cột của các quân ở hàng 1, hàng 2, ..., hàng n, và cách đặt được chọn là cách có dãy cột nhỏ nhất theo thứ tự từ điển. Nếu không có cách đặt nào thì in -1.
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 10). | |
|---|---|---|
| Đầu ra | n số là cột (từ 1 đến n) của quân hậu ở từng hàng, cách nhau một dấu cách, hoặc -1. | |
| Test | Input | Output |
| 1 | 4 | 2 4 1 3 |
| 2 | 3 | -1 |
| 3 | 6 | 2 4 6 1 3 5 |
Bài 9. Sudoku mini
Bảng Sudoku mini gồm 4 × 4 ô, cần điền các chữ số từ 1 đến 4 sao cho mỗi hàng, mỗi cột và mỗi vùng 2 × 2 (bốn vùng ở bốn góc) đều có đủ bốn chữ số khác nhau. Một số ô đã được điền sẵn (ô trống ghi 0). Hãy điền các ô trống. Nếu có nhiều cách, in cách nhỏ nhất theo thứ tự từ điển (so sánh các số theo từng hàng từ trên xuống, trong hàng từ trái sang phải).
| Đầu vào | 4 dòng, mỗi dòng gồm 4 số nguyên từ 0 đến 4 cách nhau một dấu cách (0 là ô trống). | |
|---|---|---|
| Đầu ra | 4 dòng, mỗi dòng 4 số cách nhau một dấu cách. Nếu không điền được, in -1. | |
| Test | Input | Output |
| 1 | 1 0 0 0 0 0 3 0 0 4 0 0 0 0 0 2 | 1 3 2 4 4 2 3 1 2 4 1 3 3 1 4 2 |
| 2 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1 2 3 4 3 4 1 2 2 1 4 3 4 3 2 1 |
| 3 | 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | -1 |
Bài tập tự luyện
Bài 1. Đảo tám hướng
Bản đồ của Hổ là lưới n × m gồm ô '#' (đất) và ô '.' (biển). Lần này hai ô đất chạm nhau ở cạnh hoặc ở góc (tám hướng kề nhau) thì thuộc cùng một hòn đảo. Hỏi bản đồ có bao nhiêu hòn đảo?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | Số hòn đảo. | |
| Test | Input | Output |
| 1 | 3 4 #..# .#.. ..#. | 2 |
| 2 | 1 1 # | 1 |
Bài 2. Tìm từ trong bảng chữ
Gấu Po có một bảng chữ cái n × m và một từ w. Gấu Po muốn xem có thể ghép từ w bằng cách đi từ một ô sang ô kề cạnh (lên, xuống, trái, phải), mỗi ô chỉ dùng một lần, các chữ cái trên đường đi tạo thành đúng từ w hay không.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 6). n dòng tiếp theo, mỗi dòng gồm m chữ cái thường viết liền nhau. Dòng cuối: từ w gồm chữ cái thường, dài từ 1 đến 12 ký tự. | |
|---|---|---|
| Đầu ra | In YES nếu ghép được, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 3 4 abce sfcs adee see | YES |
| 2 | 3 4 abce sfcs adee abcb | NO |
Bài 3. Tô màu bản đồ
Bản đồ của Thỏ có n vùng đánh số từ 1 đến n và m cặp vùng có chung biên giới. Thỏ có k màu và muốn tô mỗi vùng một màu sao cho hai vùng chung biên giới có màu khác nhau. Có làm được không?
| Đầu vào | Dòng 1: ba số nguyên n, m, k (1 ≤ n ≤ 10; 0 ≤ m ≤ 30; 1 ≤ k ≤ 4). m dòng sau, mỗi dòng gồm hai số nguyên u, v (1 ≤ u < v ≤ n) cho biết vùng u và vùng v chung biên giới. | |
|---|---|---|
| Đầu ra | In YES nếu tô được, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 3 3 2 1 2 2 3 1 3 | NO |
| 2 | 3 3 3 1 2 2 3 1 3 | YES |
Bài 4. Chia ba phần bằng nhau
Hổ có n khúc gỗ, khúc thứ i dài a[i]. Hổ muốn chia các khúc gỗ thành đúng ba nhóm có tổng chiều dài bằng nhau (mỗi khúc thuộc đúng một nhóm, các nhóm đều có ít nhất một khúc). Có làm được không?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 12). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 1000). | |
|---|---|---|
| Đầu ra | In YES nếu chia được, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 6 1 2 3 3 3 6 | YES |
| 2 | 3 1 2 4 | NO |
Bài 5. Cân hai đĩa
Thỏ có n quả cân, quả thứ i nặng w[i]. Với mỗi quả cân, Thỏ có thể đặt vào đĩa trái, đĩa phải hoặc không dùng. Thỏ muốn tổng khối lượng đĩa trái trừ tổng khối lượng đĩa phải đúng bằng T. Hỏi có bao nhiêu cách đặt? Hai cách khác nhau nếu có một quả cân được đặt khác nhau.
| Đầu vào | Dòng 1: hai số nguyên n, T (1 ≤ n ≤ 12; |T| ≤ 106). Dòng 2: n số nguyên w[i] (1 ≤ w[i] ≤ 1000). | |
|---|---|---|
| Đầu ra | Số cách đặt. | |
| Test | Input | Output |
| 1 | 3 1 1 2 3 | 3 |
| 2 | 2 10 1 2 | 0 |
Bài 6. Hậu và ô cấm
Gấu Po đặt n quân hậu lên bàn cờ n × n. Có k ô bị cấm, không được đặt quân hậu vào. Hai quân hậu không được chiếu nhau (không đi qua ô cấm vẫn tính là chiếu nhau). Hỏi có bao nhiêu cách đặt?
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 9; 0 ≤ k ≤ n × n). k dòng sau, mỗi dòng gồm hai số nguyên r, c (1 ≤ r, c ≤ n) là hàng và cột của ô cấm. | |
|---|---|---|
| Đầu ra | Số cách đặt. | |
| Test | Input | Output |
| 1 | 4 0 | 2 |
| 2 | 4 1 1 2 | 1 |
Bài 7. Đi qua mọi ô
Gấu Po ở ô góc trên trái của lưới n × m và muốn đến ô góc dưới phải, đi qua mọi ô trống '.' đúng một lần (tức là đi qua hết mọi ô không phải tường, mỗi ô một lần). Mỗi bước đi sang một ô kề cạnh. Hỏi có bao nhiêu cách đi?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 5). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | Số cách đi. Dữ liệu đảm bảo hai ô xuất phát và đích đều là '.'. | |
| Test | Input | Output |
| 1 | 3 3 ... ... ... | 2 |
| 2 | 5 5 ..... ..... ..... ..... ..... | 104 |
Bài 8. Đếm nghiệm Sudoku mini
Với bảng Sudoku mini 4 × 4 như ở phần luyện tập (điền chữ số từ 1 đến 4, mỗi hàng, cột và vùng 2 × 2 đều đủ bốn chữ số khác nhau), nhưng lần này Thỏ muốn biết có bao nhiêu cách điền các ô trống khác nhau.
| Đầu vào | 4 dòng, mỗi dòng gồm 4 số nguyên từ 0 đến 4 cách nhau một dấu cách (0 là ô trống). | |
|---|---|---|
| Đầu ra | Số cách điền (0 nếu bảng cho sẵn đã mâu thuẫn). | |
| Test | Input | Output |
| 1 | 1 0 0 0 0 0 3 0 0 4 0 0 0 0 0 2 | 1 |
| 2 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 288 |
Bài 9. Thử thách (không bắt buộc): Mã đi tuần
Một quân mã đứng ở ô góc trên trái (hàng 1, cột 1) của bàn cờ n × n. Quân mã đi theo hình chữ L như trong cờ vua (đi hai ô theo một hướng rồi một ô vuông góc, tổng cộng tám hướng). Hỏi có bao nhiêu cách để quân mã đi qua mọi ô của bàn cờ, mỗi ô đúng một lần?
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 5). | |
|---|---|---|
| Đầu ra | Số cách đi. | |
| Test | Input | Output |
| 1 | 5 | 304 |
| 2 | 3 | 0 |
| 3 | 1 | 1 |
-
Gợi ý chung: Khi đi trên lưới, luôn kiểm tra theo thứ tự: (1) chưa ra ngoài bảng, (2) không phải tường, (3) chưa đi qua. Hai điều kiện đầu phải được viết trước khi truy cập g[nx][ny], nếu không có thể truy cập ngoài mảng. Đếm đường đi thì phải xóa dấu vis khi quay lui, còn loang đếm vùng thì không được xóa.
-
Lưu ý thêm: Với hàm bool dừng sớm, nhớ hủy lựa chọn đúng lúc: nếu hàm sẽ trả true thì sau đó không cần xóa dấu nữa; nếu trả về false thì phải xóa dấu rồi mới thử lựa chọn khác. Mỗi lần thử, em hãy ước lượng số trạng thái (ví dụ 3^n, n!, 4^(n × m)) để chắc chắn chương trình đủ nhanh.