Hướng dẫn giải của Quân Pháo cờ Tướng
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu tìm số bước đi ít nhất của một quân Pháo (cannon) trên bàn cờ tướng để ăn được một quân địch. Quân Pháo di chuyển tự do theo hàng ngang và hàng dọc, nhưng để ăn quân địch, nó phải nhảy qua đúng một quân cờ (củng hoặc đối thủ) nằm giữa nó và quân địch theo một đường thẳng (hàng ngang hoặc hàng dọc). Tuy nhiên, trong bài toán này, vị trí của quân cờ dùng để nhảy (y3, x3) là cố định và đã cho trước. Do đó, chúng ta cần tìm đường đi ngắn nhất từ vị trí xuất phát (y1, x1) đến một vị trí nào đó mà từ đó Pháo có thể ăn được quân địch (y2, x2) bằng cách dùng quân cờ tại (y3, x3) làm vật cản nhảy.
Nói cách khác, Pháo cần đến được một ô 'công kích' nằm trên cùng hàng hoặc cột với quân địch và quân cờ nhảy, sao cho Pháo, quân cờ nhảy, và quân địch nằm trên một đường thẳng và quân cờ nhảy nằm giữa Pháo và quân địch. Vì Pháo di chuyển tự do (không bị chặn bởi các quân khác trừ khi dùng để nhảy), bài toán này về cơ bản là tìm đường đi ngắn nhất trên đồ thị các ô cờ với các bước di chuyển 4 hướng (trên, dưới, trái, phải).
Các cách tiếp cận
Cách BFS (Breadth-First Search)
#include <bits/stdc++.h>
using namespace std;
const int ROW = 10, COL = 9;
int dist[10][9];
// Kiểm tra xem tọa độ có nằm trong bàn cờ không
bool inBoard(int y, int x) {
return y >= 0 && y < ROW && x >= 0 && x < COL;
}
// Kiểm tra xem từ vị trí hiện tại (y, x) có thể ăn được quân địch (y2, x2) không
// Sử dụng quân cờ tại (y3, x3) làm vật cản
bool canAttack(int y, int x, int y2, int x2, int y3, int x3) {
// Kiểm tra hàng ngang
if (y == y2 && y == y3) {
int min_x = min(x, x2);
int max_x = max(x, x2);
// Quân cờ (y3, x3) phải nằm giữa (y, x) và (y2, x2)
if (x3 > min_x && x3 < max_x) return true;
}
// Kiểm tra hàng dọc
if (x == x2 && x == x3) {
int min_y = min(y, y2);
int max_y = max(y, y2);
// Quân cờ (y3, x3) phải nằm giữa (y, x) và (y2, x2)
if (y3 > min_y && y3 < max_y) return true;
}
return false;
}
int bfs(int y1, int x1, int y2, int x2, int y3, int x3) {
// Khởi tạo khoảng cách là -1 (chưa thăm)
memset(dist, -1, sizeof(dist));
queue<pair<int, int>> q;
q.push({y1, x1});
dist[y1][x1] = 0;
// Mảng hướng di chuyển: Trái, Phải, Lên, Xuống
int dy[] = {0, 0, -1, 1};
int dx[] = {-1, 1, 0, 0};
while (!q.empty()) {
pair<int, int> u = q.front();
q.pop();
int y = u.first;
int x = u.second;
// Kiểm tra nếu từ ô hiện tại có thể ăn được quân địch
if (canAttack(y, x, y2, x2, y3, x3)) {
return dist[y][x] + 1; // Trả về số bước đi + 1 nước ăn
}
// Duyệt các hướng di chuyển
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
// Nếu ô tiếp theo hợp lệ và chưa được thăm
if (inBoard(ny, nx) && dist[ny][nx] == -1) {
dist[ny][nx] = dist[y][x] + 1;
q.push({ny, nx});
}
}
}
return -1; // Không tìm được đường đi
}
int main() {
int y1, x1, y2, x2, y3, x3;
cin >> y1 >> x1 >> y2 >> x2 >> y3 >> x3;
cout << bfs(y1, x1, y2, x2, y3, x3) << endl;
return 0;
}
- Time Complexity: O(R * C) ~ O(90)
- Space Complexity: O(R * C) ~ O(90)
Đây là cách tiếp cận trực quan và hiệu quả nhất cho bài toán tìm đường đi ngắn nhất trên lưới.
- Mô hình hóa bài toán: Bàn cờ được coi là một đồ thị, mỗi ô là một node. Các ô kề nhau (trên, dưới, trái, phải) có cạnh nối đến nhau.
- Tìm điểm đến: Thay vì xác định một điểm đến cố định, ta thay đổi điều kiện dừng của BFS. BFS sẽ dừng ngay khi nó thăm một ô
(y, x)mà tại đó Pháo có thể ăn được quân địch. Điều này có nghĩa là(y, x)phải nằm trên cùng hàng hoặc cột với(y2, x2)và(y3, x3), và(y3, x3)phải nằm giữa(y, x)và(y2, x2). Vị trí(y, x)này chính là vị trí Pháo cần đến trước khi thực hiện nước ăn. - Thực thi BFS:
- Khởi tạo hàng đợi với vị trí xuất phát
(y1, x1)và khoảng cách 0. - Tại mỗi bước BFS, lấy vị trí hiện tại
(y, x)ra. - Kiểm tra điều kiện
canAttack(y, x, ...). Nếu thỏa mãn, trả vềdist[y][x] + 1(số bước đến(y, x)cộng 1 nước ăn). - Nếu chưa, thêm các ô kề hợp lệ vào hàng đợi.
- Khởi tạo hàng đợi với vị trí xuất phát
- Độ phức tạp: Với bàn cờ 10x9 (~90 ô), BFS chạy rất nhanh, độ phức tạp thời gian và bộ nhớ đều là O(90), không đáng kể.
Cách Phương pháp Phân tích Vị trí (Geometry Analysis)
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
int main() {
int y1, x1, y2, x2, y3, x3;
cin >> y1 >> x1 >> y2 >> x2 >> y3 >> x3;
// Kiểm tra nếu Pháo đang ở vị trí có thể ăn ngay
// (Cần kiểm tra điều kiện nhảy qua y3)
bool can_start_eat = false;
if (y1 == y2 && y1 == y3 && x3 > min(x1, x2) && x3 < max(x1, x2)) can_start_eat = true;
if (x1 == x2 && x1 == x3 && y3 > min(y1, y2) && y3 < max(y1, y2)) can_start_eat = true;
if (can_start_eat) {
cout << 1 << endl;
return 0;
}
int min_steps = 1e9;
// Xét các trường hợp Pháo có thể đến ăn
// Trường hợp 1: Ăn theo hàng ngang
if (y2 == y3) {
// Pháo cần đến một cột x' sao cho (y2, x') -> (y2, x2) có (y3, x3) ở giữa
// Điều đó có nghĩa là x' và x2 nằm ở 2 phía khác nhau của x3.
// Hoặc x' và x2 nằm cùng phía nhưng x3 không ở giữa.
// Thực tế, để (y3, x3) nằm giữa, ta cần:
// Pháo tại (y', x') -> Ăn (y2, x2) qua (y3, x3)
// Điều kiện: y' = y2 = y3? Không, Pháo phải nằm trên hàng ngang đó.
// Vậy Pháo nằm ở hàng y2.
// Cần tìm x' thỏa: x' và x2 nằm 2 bên x3.
// Tức là (x' < x3 < x2) hoặc (x2 < x3 < x').
// Nếu x' == x2 thì không ăn được (không có vật cản).
// Vậy có 2 vị trí 'công kích' cố định:
// 1. Xét bên trái x3: nếu x3 > x2, vị trí là (y2, x3 + 1) hoặc đi về phía đó.
// Thực ra vị trí chính xác là (y2, x') sao cho x' và x2 ở 2 bên x3.
// Nếu x2 < x3, thì x' phải > x3.
// Nếu x2 > x3, thì x' phải < x3.
// Chỉ có 2 hướng.
// Xác định các vị trí đích (target positions) có thể ăn được:
int target_x_1 = -1, target_x_2 = -1;
if (x2 < x3) target_x_1 = x3 + 1; // Pháo ở bên phải x3
if (x2 > x3) target_x_1 = x3 - 1; // Pháo ở bên trái x3
// Nếu x2 == x3, không thể ăn (quân địch và quân nhảy trùng nhau, hoặc không có vật cản đúng nghĩa)
// Giả sử input hợp lệ, x2 != x3.
// Tính khoảng cách Manhattan từ (y1, x1) đến các vị trí đích này
if (target_x_1 != -1 && target_x_1 >= 0 && target_x_1 < 9) {
// Nếu Pháo đang ở hàng y2 và cột nằm giữa x3 và target_x_1?
// Không, Pháo có thể di chuyển tự do.
// Đường đi ngắn nhất đến (y2, target_x_1) là |y1 - y2| + |x1 - target_x_1|
int dist = abs(y1 - y2) + abs(x1 - target_x_1);
// +1 nước ăn
min_steps = min(min_steps, dist + 1);
}
}
// Trường hợp 2: Ăn theo hàng dọc
if (x2 == x3) {
int target_y_1 = -1;
if (y2 < y3) target_y_1 = y3 + 1;
if (y2 > y3) target_y_1 = y3 - 1;
if (target_y_1 != -1 && target_y_1 >= 0 && target_y_1 < 10) {
int dist = abs(x1 - x2) + abs(y1 - target_y_1);
min_steps = min(min_steps, dist + 1);
}
}
if (min_steps > 1000) cout << -1 << endl;
else cout << min_steps << endl;
return 0;
}
- Time Complexity: O(1)
- Space Complexity: O(1)
Phương pháp này dựa trên việc phân tích hình học của thế cờ.
- Vị trí công kích: Quân Pháo chỉ có thể ăn được nếu nó nằm ở một vị trí cụ thể trên cùng hàng hoặc cột với quân địch và quân nhảy. Do quân nhảy
(y3, x3)là cố định, nên các vị trí mà Pháo cần đến (sau khi đã di chuyển) cũng rất hạn chế.- Nếu ăn theo hàng ngang: Pháo phải ở hàng
y2(hoặcy3vìy2=y3). Vị trí cộtx'của Pháo phải nằm ở phía đối diện so vớix2quax3. Ví dụ, nếux2 < x3, Pháo cần ởx' > x3. Khoảng cách di chuyển từ(y1, x1)đến(y2, x')là|y1 - y2| + |x1 - x'|. - Tương tự cho hàng dọc.
- Nếu ăn theo hàng ngang: Pháo phải ở hàng
- Trường hợp đặc biệt: Nếu Pháo ngay từ đầu đã ở vị trí có thể ăn (đủ điều kiện nhảy qua
y3), đáp án là 1. - Tính toán: Thay vì BFS, ta chỉ cần tính khoảng cách Manhattan (tốc độ di chuyển tối ưu giữa các ô vuông) từ điểm xuất phát đến 1 hoặc 2 vị trí công kích có thể có. Nếu Pháo không thể đến vị trí đó (ví dụ nằm ngoài bàn cờ) hoặc không có vị trí công kích hợp lệ, trả về -1.
- Ưu điểm: Rất nhanh, độ phức tạp hằng số O(1). Tuy nhiên, nó chỉ hiệu quả khi quân nhảy là cố định.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(R * C) ~ O(90) | O(R * C) ~ O(90) | BFS (Breadth-First Search) |
| 2 | O(1) | O(1) | Phương pháp Phân tích Vị trí (Geometry Analysis) |
Bài học kinh nghiệm
- Vấn đề có thể được chuyển đổi thành bài toán tìm đường đi ngắn nhất trên lưới, trong đó đích đến là các ô cho phép Pháo thực hiện nước ăn (nhảy qua quân cờ tại (y3, x3) để ăn (y2, x2)).
- Vì Pháo di chuyển tự do (không bị giới hạn bởi các quân cờ khác trên đường đi, trừ vật cản để nhảy), ta có thể dùng BFS để tìm đường đi ngắn nhất hoặc tính trực tiếp khoảng cách Manhattan nếu phân tích kỹ điều kiện.
Lỗi thường gặp
- Quên kiểm tra xem quân cờ nhảy (y3, x3) có thực sự nằm giữa Pháo và quân địch hay không khi kiểm tra điều kiện ăn.
- Lầm tưởng rằng Pháo cần nhảy qua nhiều quân cờ. Quy tắc cờ tướng chỉ cần 1 quân cờ ở giữa.
- Bỏ qua trường hợp Pháo có thể ăn ngay lập tức nếu đang ở vị trí hợp lệ (số bước là 1).
Bình luận