VOJ - KANDP
Source: KANDP
Tags: Greedy, Maths, Graph
Problem:
Trên một bàn cờ vua kích thước vô hạn có một quân mã và một quân tốt. Vị trí của quân mã là (Kx, Ky), vị trí quân tốt là (Px, Py), trong đó x là chỉ số dòng và y là chỉ số cột. Quân mã được truyền đi theo 8 hướng như bàn cờ vua chuẩn. Quân tốt chỉ được đi một hướng xuống (từ ô (Px, Py) đến ô (Px - 1, Py)). Hai quân cờ di chuyển theo lượt, xen kẽ nhau. Khi một quân cờ vào vị trí của quân cờ khác đang đứng thì quân cờ vừa di chuyển sẽ thắng.
Cho biết vị trí ban đầu của quân mã và quân tốt, quân cờ nào đi trước. Hãy tính xem quân mã có khả năng thắng không, nếu có in ra YES và số bước ít nhất để quân mã ăn được quân tốt, ngược lại in ra NO.
Các số nguyên Kx, Ky, Px, Py có giá trị tuyệt đối không vượt quá 1000.
Trong input, 2 dòng đầu chứa số tọa độ quân mã và quân tốt, dòng cuối chứa số 0/1 thể hiện quân mã/quân tốt đi trước.
Ví dụ:
Input:
0 0
0 3
0
Output:
YES
2
Explanation:
Solution:
Giả sử quân mã ăn được quân tốt ở ô (x, y), nếu quân mã đi trước thì số bước để quân mã đi đến ô đó phải nhiều hơn số bước quân tốt đi đến ô đó 1 bước, nếu quân tốt đi trước thì số bước để quân mã đi đến ô đó phải bằng số bước quân tốt đi đến ô đó. Điều này giải thích đơn giản thôi, 2 quân cùng đến một ô với số bước bằng nhau, quân nào đi sau sẽ ăn được quân đi trước.
Gọi d[x][y] là số bước tối thiểu để quân mã đi đến ô (x, y) và k = Px - x là số bước để quân tốt đi đến ô (x, y) (tất nhiên là y = Py). Nếu quân mã đi đến một ô trên đường đi của quân tốt trước nó, thì quân mã có thể đi qua đi lại chờ tới khi quân tốt đi đến, vì mỗi lần đi qua lại tốn 2 bước, nên nếu số bước cần thiết để quân mã ăn quân tốt ở ô này cách số bước ít nhất mà nó tới là số chẵn thì quân mã có thể ăn được quân tốt tại ô (x, y). Sẽ không có trường hợp quân mã đi số lẻ bước để quay lại vị trí đang đứng vì mỗi bước quân mã sẽ đi qua một ô khác màu, vậy muốn quay về ô đang đứng, nó luôn phải đi từ ô đang đứng sang ô khác màu rồi sang cùng màu rồi khác màu... cứ như vậy nên luôn phải là số chẵn.
Nói cách khác:
- Trường hợp quân mã đi trước, nếu k + 1 - d[x][y] chẵn thì quân mã có thể ăn quân tốt (vì đi trước nên quân mã cần phải tới sau quân tốt 1 bước)
- Trường hợp quân mã đi sau, nếu k - d[x][y] chẵn thì quân mã mới có thể ăn quân tốt.
Nhận xét ra được điều này rồi sẽ giúp chúng ta tránh phải liệt kê ra các đường đi vòng vèo cho đủ số bước cần thiết. Và từ nhận xét này ta có 2 hướng làm được trình bày ở dưới.
Approach 1:
Ở hướng làm này ta sẽ sử dụng phương pháp duyệt BFS để tính d[x][y]. Nhưng vấn đề là, với bàn cờ vô hạn thì biết giới hạn đâu để mà BFS? Nhận xét một tí, đầu tiên ta thấy giới hạn chỉ mở rộng về phần âm của giới hạn x, vì quân tốt chỉ có thể đi lùi, còn quân mã thì muốn "xực" quân tốt nên nó cũng đi theo quân tốt nốt. Vậy giờ ta đã có các giới hạn như sau d[? → 1000][1000 → 1000]. Giờ tới chuyên mục điền vào dấu hỏi, con số phù hợp là gì?
Giả sử trường hợp tệ nhất là quân mã ở xa quân tốt nhất có thể và còn ở trên nữa, đó là Px = -1000 và Kx = 1000. Đầu tiên muốn chặn đầu ăn quân tốt, quân mã phải đuổi kịp đã. Mỗi bước quân tốt đi từ x đến x - 1 còn quân mã có thể đi từ x đến x - 2, vậy cần ít nhất là Kx - Px bước để quân mã đuổi kịp (đuổi kịp thôi chưa chắc ăn được nhé). Tọa độ 2 quân lúc mã đuổi kịp tốt trong trường hợp xấu nhất là -3000. Rồi sau khi đã đuổi kịp, thì cần bao nhiêu bước nữa để mã ăn tốt? Để ý rằng trong worst case hoặc bất kỳ case nào, với 2000 bước thì chắc chắn mã có thể đứng kế bên say hi với con tốt (hoặc không thì là rất gần). Vậy ta khảo sát khi quân mã ở ô (0, 0) và quân tốt ở ô (0, i) với i = 1 → 5 sẽ tính được số bước tối thiểu để quân mã ăn quân tốt là k. Khi này ta dễ dàng chứng minh được, trong vòng 2000 + k bước, kiểu gì con mã cũng phải ăn được con tốt, nếu không thì là do con mã đứng ở vị trí không ăn được, hoặc do con mã cùi bắp. Giới hạn lúc này là d[-3000 - k → 1000][-1000 → 1000]. Vậy k là bao nhiêu? Xin giới thiệu k là một con số bí ẩn!!! (bí ẩn vì tui cũng chưa khảo sát nữa ._. nhưng có thể ngắm chừng là k < 500 :">).
Ngoài ra còn một số cái lặt vặt như sau:
Q: Có trường hợp nào con mã bị ăn không? Chứ em thấy nó không ăn con tốt thì thôi chứ sao con tốt ăn được con mã? (from nhoxsky184, 696969 votes)
A: Nếu con mã đứng ngay dưới con tốt và con tốt đi trước, thì con mã xác định lên dĩa rồi :v (cơ mà test không có trường hợp này ._.)
Q: Nếu d[x][y] đúng bằng số bước mà con mã đi vào đó là bị con tốt ăn, thì có push vào queue không? (from cobengocnghechyeumauhuongghetsugiadoi, 12345 votes)
A: Nếu cẩn thận thì không push cũng được, cơ mà chứng minh được là có push hay không cũng không ảnh hưởng đến các kết quả khác nên mình vẫn push để đỡ code lằng nhằng.
Q: Giả sử con mã cần vượt qua 3 giới hạn kia để mà tới được vị trí nhỏ nhất thì sao? (from toidaluaanhembaogiochua, -∞ votes)
A: Thật ra cũng chứng minh được là nó hoàn toàn có một đường đối xứng để đến được đường đi nhỏ nhất ấy mà không cần nhất thiết phải vượt qua giới hạn, nhưng nếu muốn chắc thì cũng có thể để dư giới hạn ra một chút.
Độ phức tạp O(8e6).
Code:
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
#define _ 3500 +
const int dirX[8] = {-2, -2, -1, 1, 2, 2, 1, -1},
dirY[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
int kx, ky, px, py, turn, d[4515][4515], res = 1e9;
queue <pair <int, int> > bfs;
int main() {
cin >> kx >> ky >> px >> py >> turn;
if (kx == px - 1 && ky == py && turn) {
cout << "NO"; return 0;
}
memset(d, -1, sizeof d);
d[_ kx][_ ky] = 0;
bfs.push({kx, ky});
while (!bfs.empty()) {
int curX = bfs.front().first;
int curY = bfs.front().second;
bfs.pop();
for (int i = 0; i < 8; i++) {
int x = curX + dirX[i];
int y = curY + dirY[i];
if (x < -3000 || 1000 < x || y < -1000 || 1000 < y || d[_ x][_ y] > -1)
continue;
d[_ x][_ y] = d[_ curX][_ curY] + 1;
bfs.push({x, y});
int tmp = px - x + 1 - turn;
if (x <= px && y == py && d[_ x][_ y] <= tmp && (tmp - d[_ x][_ y]) % 2 == 0)
res = min(res, tmp);
}
}
res < 1e9 ? cout << "YES\n" << res : cout << "NO";
}
Approach 2:
Vì hướng tiếp cận này mà mình đã dành 3 ngày để chứng minh :v Nhận thấy điều ta quan tâm thật sự chỉ là d[x][y] với những tọa độ x ≤ Px và y = Py thôi, và nếu đã có d[x][y] thì rõ ràng d[x - 1][y] không quan trọng nữa, điều này dẫn đến một suy nghĩ là có công thức O(1) nào để tính ra d[x][y] không? Và câu trả lời là CÓ!!!
(Phần chứng minh khá dài, nếu chỉ muốn lấy công thức có thể skip đến phần code ở dưới cùng)
Trước tiên, làm sao để biết là quân mã có thể ăn quân tốt hay không ngay từ lúc đọc input? Quân mã mỗi lần di chuyển sẽ di chuyển sang một ô khác màu với ô nó đang đứng hiện tại, và quân tốt cũng vậy. Vậy bước cuối cùng trước khi ăn được quân tốt, quân mã phải đứng ở ô khác màu với quân tốt, nói cách khác, nếu quân tốt luôn ở ô cùng màu với quân mã lúc quân mã di chuyển, quân mã sẽ không bao giờ chạm được quân tốt.
Vậy ta có điều kiện loại trừ như sau:
- Nếu quân mã và quân tốt đứng ở 2 ô cùng màu và quân mã đi trước → NO.
- Nếu quân mã và quân tốt đứng ở 2 ô khác màu và quân tốt đi trước → NO.
Và ta có thể công thức hóa nó như sau (turn là biến cho biết quân nào đi trước theo đề bài):
if (Kx + Ky + Px + Py) % 2 = turn then return NO
Bây giờ chúng ta bắt đầu đi vào phần công thức tính d[x][y]:
Đầu tiên ta dễ dàng thấy một quân mã đi từ ô (0, 0) đến ô (5, 5) và một quân mã đi từ ô (3, 4) đến ô (8, 9) là như nhau, vì chúng có cùng khoảng cách. Vậy điều ta quan tâm là số bước tối thiểu để con mã đi từ ô nó đang đứng đến ô cách nó x dòng và y cột. Do đó ta đơn giản hóa nó thành bài toán số bước ít nhất để con mã đi từ ô (0, 0) đến ô (x, y).
Nếu x = 1, y = 0 thì kết quả là 3.
Nếu x = 2, y = 2 thì kết quả là 4.
2 bài toán trên không có cấu trúc giống các bài toán còn lại, nên ta lưu kết quả đã được tính sẵn của chúng. Còn lại, ta chia không gian bàn cờ thành các vùng như trên. Vì (x, y) và (y, x) sẽ có cùng đáp án, nên ta sẽ quy định luôn là x > y. (x cột, y dòng, mọi thứ đều là tương đối nên đừng bắt bẻ mình huhu :<)
Vùng màu xanh lá và xanh dương là phần chứa những ô có cùng tính chất như sau: chỉ đi bằng những bước x + 2, y + 1 hoặc x + 2, y - 1 và thêm không quá 2 bước khác để tới ô đấy. (do ta chỉ xét x > y nên chỉ quan tâm đến vùng xanh dương phía trên)
Vùng màu xanh lá và trắng là phần chứ những ô có cùng tính chất như sau: chỉ đi bằng những bước x + 2, y + 1 và x + 1, y + 2 và thêm không quá 2 bước khác để tới ô đấy. (vùng màu xanh lá là đường giới hạn và cũng là phần giao, những ô chỉ đi bằng các bước x + 2, y + 1 và thêm không quá 2 bước khác để tới ô đấy)
Công thức ở 2 vùng này sẽ khác nhau, nhưng trước hết ta cần biết cách xác định vùng đã.
if y = 0 or x / y ≥ 2 then (x, y) thuộc vùng 1
else (x, y) thuộc vùng 2
Ở vùng 1, vì ta luôn đi các bước x + 2 và y chỉ tăng tối đa 1, nên x / y luôn không nhỏ hơn 2, trường hợp khác là y = 0 cũng nằm trong vùng này.
Sau khi đã xác định được bài toán cần tìm nằm ở vùng nào, ta sẽ đi đến công thức:
Lưu ý, phép chia / trong các công thức dưới đây là phép chia lấy phần nguyên.
Vùng 1:
Nếu x % 4 = 0:
Nếu y % 2 = 0, ta luôn có thể đi tới những ô này bằng các bước x + 2, y + 1 hoặc x + 2, y - 1 mà không cần thêm bất kỳ bước nào, do đó số bước đi đến ô này sẽ là x / 2.
Nếu y % 2 = 1, với những ô này, đầu tiên đi giống bài toán y % 2 = 0, nhưng ở bước cuối cùng thì thay bằng 2 bước x + 1, y + 2 và x + 1, y - 2, do đó số bước đi đến ô này sẽ là x / 2 + 1.
Nếu x % 4 = 1:
Nếu y % 2 = 0, ta đi đến cột x % 4 = 0 kề trước nó và đi bằng 1 bước x + 1, y + 2 hoặc x + 1, y - 2, do đó số bước đi đến ô này sẽ là x / 2 + 1.
Nếu y % 2 = 1, ta đi đến cột x % 4 = 0 kề trước nó và đi bằng 2 bước x - 1, y + 2 và x + 2, y - 1, do đó số bước đi đến ô này sẽ là x / 2 + 2.
Nếu x % 4 = 2 và x % 4 = 3:
Ở 2 cột này công thức tương đối giống với x % 4 = 0 và x % 4 = 1 nhưng khác ở chỗ là nó bị ngược lại ở dòng y % 2. Do đó các công thức được đổi thành như sau:
Nếu x % 4 = 2:
Nếu y % 2 = 0: số bước đi đến ô này sẽ là x / 2 + 1.
Nếu y % 2 = 1: số bước đi đến ô này sẽ là x / 2.
Tags: Greedy, Maths, Graph
Problem:
Trên một bàn cờ vua kích thước vô hạn có một quân mã và một quân tốt. Vị trí của quân mã là (Kx, Ky), vị trí quân tốt là (Px, Py), trong đó x là chỉ số dòng và y là chỉ số cột. Quân mã được truyền đi theo 8 hướng như bàn cờ vua chuẩn. Quân tốt chỉ được đi một hướng xuống (từ ô (Px, Py) đến ô (Px - 1, Py)). Hai quân cờ di chuyển theo lượt, xen kẽ nhau. Khi một quân cờ vào vị trí của quân cờ khác đang đứng thì quân cờ vừa di chuyển sẽ thắng.
Cho biết vị trí ban đầu của quân mã và quân tốt, quân cờ nào đi trước. Hãy tính xem quân mã có khả năng thắng không, nếu có in ra YES và số bước ít nhất để quân mã ăn được quân tốt, ngược lại in ra NO.
Các số nguyên Kx, Ky, Px, Py có giá trị tuyệt đối không vượt quá 1000.
Trong input, 2 dòng đầu chứa số tọa độ quân mã và quân tốt, dòng cuối chứa số 0/1 thể hiện quân mã/quân tốt đi trước.
Ví dụ:
Input:
0 0
0 3
0
Output:
YES
2
Explanation:
 |
| Trong hình trên, K chỉ vị trí quân mã, P chỉ vị trí quân tốt |
Solution:
Giả sử quân mã ăn được quân tốt ở ô (x, y), nếu quân mã đi trước thì số bước để quân mã đi đến ô đó phải nhiều hơn số bước quân tốt đi đến ô đó 1 bước, nếu quân tốt đi trước thì số bước để quân mã đi đến ô đó phải bằng số bước quân tốt đi đến ô đó. Điều này giải thích đơn giản thôi, 2 quân cùng đến một ô với số bước bằng nhau, quân nào đi sau sẽ ăn được quân đi trước.
Gọi d[x][y] là số bước tối thiểu để quân mã đi đến ô (x, y) và k = Px - x là số bước để quân tốt đi đến ô (x, y) (tất nhiên là y = Py). Nếu quân mã đi đến một ô trên đường đi của quân tốt trước nó, thì quân mã có thể đi qua đi lại chờ tới khi quân tốt đi đến, vì mỗi lần đi qua lại tốn 2 bước, nên nếu số bước cần thiết để quân mã ăn quân tốt ở ô này cách số bước ít nhất mà nó tới là số chẵn thì quân mã có thể ăn được quân tốt tại ô (x, y). Sẽ không có trường hợp quân mã đi số lẻ bước để quay lại vị trí đang đứng vì mỗi bước quân mã sẽ đi qua một ô khác màu, vậy muốn quay về ô đang đứng, nó luôn phải đi từ ô đang đứng sang ô khác màu rồi sang cùng màu rồi khác màu... cứ như vậy nên luôn phải là số chẵn.
Nói cách khác:
- Trường hợp quân mã đi trước, nếu k + 1 - d[x][y] chẵn thì quân mã có thể ăn quân tốt (vì đi trước nên quân mã cần phải tới sau quân tốt 1 bước)
- Trường hợp quân mã đi sau, nếu k - d[x][y] chẵn thì quân mã mới có thể ăn quân tốt.
Nhận xét ra được điều này rồi sẽ giúp chúng ta tránh phải liệt kê ra các đường đi vòng vèo cho đủ số bước cần thiết. Và từ nhận xét này ta có 2 hướng làm được trình bày ở dưới.
Approach 1:
Ở hướng làm này ta sẽ sử dụng phương pháp duyệt BFS để tính d[x][y]. Nhưng vấn đề là, với bàn cờ vô hạn thì biết giới hạn đâu để mà BFS? Nhận xét một tí, đầu tiên ta thấy giới hạn chỉ mở rộng về phần âm của giới hạn x, vì quân tốt chỉ có thể đi lùi, còn quân mã thì muốn "xực" quân tốt nên nó cũng đi theo quân tốt nốt. Vậy giờ ta đã có các giới hạn như sau d[? → 1000][1000 → 1000]. Giờ tới chuyên mục điền vào dấu hỏi, con số phù hợp là gì?
Giả sử trường hợp tệ nhất là quân mã ở xa quân tốt nhất có thể và còn ở trên nữa, đó là Px = -1000 và Kx = 1000. Đầu tiên muốn chặn đầu ăn quân tốt, quân mã phải đuổi kịp đã. Mỗi bước quân tốt đi từ x đến x - 1 còn quân mã có thể đi từ x đến x - 2, vậy cần ít nhất là Kx - Px bước để quân mã đuổi kịp (đuổi kịp thôi chưa chắc ăn được nhé). Tọa độ 2 quân lúc mã đuổi kịp tốt trong trường hợp xấu nhất là -3000. Rồi sau khi đã đuổi kịp, thì cần bao nhiêu bước nữa để mã ăn tốt? Để ý rằng trong worst case hoặc bất kỳ case nào, với 2000 bước thì chắc chắn mã có thể đứng kế bên say hi với con tốt (hoặc không thì là rất gần). Vậy ta khảo sát khi quân mã ở ô (0, 0) và quân tốt ở ô (0, i) với i = 1 → 5 sẽ tính được số bước tối thiểu để quân mã ăn quân tốt là k. Khi này ta dễ dàng chứng minh được, trong vòng 2000 + k bước, kiểu gì con mã cũng phải ăn được con tốt, nếu không thì là do con mã đứng ở vị trí không ăn được, hoặc do con mã cùi bắp. Giới hạn lúc này là d[-3000 - k → 1000][-1000 → 1000]. Vậy k là bao nhiêu? Xin giới thiệu k là một con số bí ẩn!!! (bí ẩn vì tui cũng chưa khảo sát nữa ._. nhưng có thể ngắm chừng là k < 500 :">).
Ngoài ra còn một số cái lặt vặt như sau:
Q: Có trường hợp nào con mã bị ăn không? Chứ em thấy nó không ăn con tốt thì thôi chứ sao con tốt ăn được con mã? (from nhoxsky184, 696969 votes)
A: Nếu con mã đứng ngay dưới con tốt và con tốt đi trước, thì con mã xác định lên dĩa rồi :v (cơ mà test không có trường hợp này ._.)
Q: Nếu d[x][y] đúng bằng số bước mà con mã đi vào đó là bị con tốt ăn, thì có push vào queue không? (from cobengocnghechyeumauhuongghetsugiadoi, 12345 votes)
A: Nếu cẩn thận thì không push cũng được, cơ mà chứng minh được là có push hay không cũng không ảnh hưởng đến các kết quả khác nên mình vẫn push để đỡ code lằng nhằng.
Q: Giả sử con mã cần vượt qua 3 giới hạn kia để mà tới được vị trí nhỏ nhất thì sao? (from toidaluaanhembaogiochua, -∞ votes)
A: Thật ra cũng chứng minh được là nó hoàn toàn có một đường đối xứng để đến được đường đi nhỏ nhất ấy mà không cần nhất thiết phải vượt qua giới hạn, nhưng nếu muốn chắc thì cũng có thể để dư giới hạn ra một chút.
Độ phức tạp O(8e6).
Code:
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
#define _ 3500 +
const int dirX[8] = {-2, -2, -1, 1, 2, 2, 1, -1},
dirY[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
int kx, ky, px, py, turn, d[4515][4515], res = 1e9;
queue <pair <int, int> > bfs;
int main() {
cin >> kx >> ky >> px >> py >> turn;
if (kx == px - 1 && ky == py && turn) {
cout << "NO"; return 0;
}
memset(d, -1, sizeof d);
d[_ kx][_ ky] = 0;
bfs.push({kx, ky});
while (!bfs.empty()) {
int curX = bfs.front().first;
int curY = bfs.front().second;
bfs.pop();
for (int i = 0; i < 8; i++) {
int x = curX + dirX[i];
int y = curY + dirY[i];
if (x < -3000 || 1000 < x || y < -1000 || 1000 < y || d[_ x][_ y] > -1)
continue;
d[_ x][_ y] = d[_ curX][_ curY] + 1;
bfs.push({x, y});
int tmp = px - x + 1 - turn;
if (x <= px && y == py && d[_ x][_ y] <= tmp && (tmp - d[_ x][_ y]) % 2 == 0)
res = min(res, tmp);
}
}
res < 1e9 ? cout << "YES\n" << res : cout << "NO";
}
Approach 2:
Vì hướng tiếp cận này mà mình đã dành 3 ngày để chứng minh :v Nhận thấy điều ta quan tâm thật sự chỉ là d[x][y] với những tọa độ x ≤ Px và y = Py thôi, và nếu đã có d[x][y] thì rõ ràng d[x - 1][y] không quan trọng nữa, điều này dẫn đến một suy nghĩ là có công thức O(1) nào để tính ra d[x][y] không? Và câu trả lời là CÓ!!!
(Phần chứng minh khá dài, nếu chỉ muốn lấy công thức có thể skip đến phần code ở dưới cùng)
Trước tiên, làm sao để biết là quân mã có thể ăn quân tốt hay không ngay từ lúc đọc input? Quân mã mỗi lần di chuyển sẽ di chuyển sang một ô khác màu với ô nó đang đứng hiện tại, và quân tốt cũng vậy. Vậy bước cuối cùng trước khi ăn được quân tốt, quân mã phải đứng ở ô khác màu với quân tốt, nói cách khác, nếu quân tốt luôn ở ô cùng màu với quân mã lúc quân mã di chuyển, quân mã sẽ không bao giờ chạm được quân tốt.
Vậy ta có điều kiện loại trừ như sau:
- Nếu quân mã và quân tốt đứng ở 2 ô cùng màu và quân mã đi trước → NO.
- Nếu quân mã và quân tốt đứng ở 2 ô khác màu và quân tốt đi trước → NO.
Và ta có thể công thức hóa nó như sau (turn là biến cho biết quân nào đi trước theo đề bài):
if (Kx + Ky + Px + Py) % 2 = turn then return NO
Bây giờ chúng ta bắt đầu đi vào phần công thức tính d[x][y]:
(Các công thức dựa trên câu trả lời của Arielr trong câu hỏi của Kyle Hughes trên Stack Overflow về vấn đề này. Câu trả lời rất chính xác nhưng chỉ có 10 votes nên nằm tuốt dưới lol xD trong câu trả lời của Arielr không có ghi nguồn công thức anh ta tìm được nên mình chỉ dẫn tới câu trả lời đấy, trong đó cũng không có phần chứng minh, phần chứng minh công thức là do mình tự chứng minh trong 3 ngày qua, cũng như đã đơn giản hóa hơn rất nhiều so với công thức gốc trong câu trả lời của anh)
Đầu tiên ta dễ dàng thấy một quân mã đi từ ô (0, 0) đến ô (5, 5) và một quân mã đi từ ô (3, 4) đến ô (8, 9) là như nhau, vì chúng có cùng khoảng cách. Vậy điều ta quan tâm là số bước tối thiểu để con mã đi từ ô nó đang đứng đến ô cách nó x dòng và y cột. Do đó ta đơn giản hóa nó thành bài toán số bước ít nhất để con mã đi từ ô (0, 0) đến ô (x, y).
Nếu x = 2, y = 2 thì kết quả là 4.
2 bài toán trên không có cấu trúc giống các bài toán còn lại, nên ta lưu kết quả đã được tính sẵn của chúng. Còn lại, ta chia không gian bàn cờ thành các vùng như trên. Vì (x, y) và (y, x) sẽ có cùng đáp án, nên ta sẽ quy định luôn là x > y. (x cột, y dòng, mọi thứ đều là tương đối nên đừng bắt bẻ mình huhu :<)
Vùng màu xanh lá và xanh dương là phần chứa những ô có cùng tính chất như sau: chỉ đi bằng những bước x + 2, y + 1 hoặc x + 2, y - 1 và thêm không quá 2 bước khác để tới ô đấy. (do ta chỉ xét x > y nên chỉ quan tâm đến vùng xanh dương phía trên)
Vùng màu xanh lá và trắng là phần chứ những ô có cùng tính chất như sau: chỉ đi bằng những bước x + 2, y + 1 và x + 1, y + 2 và thêm không quá 2 bước khác để tới ô đấy. (vùng màu xanh lá là đường giới hạn và cũng là phần giao, những ô chỉ đi bằng các bước x + 2, y + 1 và thêm không quá 2 bước khác để tới ô đấy)
Công thức ở 2 vùng này sẽ khác nhau, nhưng trước hết ta cần biết cách xác định vùng đã.
if y = 0 or x / y ≥ 2 then (x, y) thuộc vùng 1
else (x, y) thuộc vùng 2
Ở vùng 1, vì ta luôn đi các bước x + 2 và y chỉ tăng tối đa 1, nên x / y luôn không nhỏ hơn 2, trường hợp khác là y = 0 cũng nằm trong vùng này.
Sau khi đã xác định được bài toán cần tìm nằm ở vùng nào, ta sẽ đi đến công thức:
Lưu ý, phép chia / trong các công thức dưới đây là phép chia lấy phần nguyên.
Vùng 1:
Nếu y % 2 = 0, ta luôn có thể đi tới những ô này bằng các bước x + 2, y + 1 hoặc x + 2, y - 1 mà không cần thêm bất kỳ bước nào, do đó số bước đi đến ô này sẽ là x / 2.
 |
| Những ô màu đỏ nhạt là những bài toán x % 4 = 0 và y % 2 = 0 |
 |
| Những ô màu đỏ là những bài toán x % 4 = 0 và y % 2 = 1 |
Nếu y % 2 = 0, ta đi đến cột x % 4 = 0 kề trước nó và đi bằng 1 bước x + 1, y + 2 hoặc x + 1, y - 2, do đó số bước đi đến ô này sẽ là x / 2 + 1.
 |
| Những ô màu đỏ nhạt là những bài toán x % 4 = 1 và y % 2 = 0 |
 |
| Những ô màu đỏ nhạt là những bài toán x % 4 = 1 và y % 2 = 1 |
Ở 2 cột này công thức tương đối giống với x % 4 = 0 và x % 4 = 1 nhưng khác ở chỗ là nó bị ngược lại ở dòng y % 2. Do đó các công thức được đổi thành như sau:
Nếu x % 4 = 2:
Nếu y % 2 = 0: số bước đi đến ô này sẽ là x / 2 + 1.
Nếu y % 2 = 1: số bước đi đến ô này sẽ là x / 2.
Nếu x % 4 = 3:
Nếu y % 2 = 0: số bước đi đến ô này sẽ là x / 2 + 2.
Nếu y % 2 = 1: số bước đi đến ô này sẽ là x / 2 + 1.
Vùng 2:
Nếu (x + y) % 3 = 0: những ô trên đường chéo phụ x + y này có thể đi đến bằng các bước x + 2, y + 1 và x + 1, y + 2 mà không cần thêm bất kỳ bước nào khác, do đó số bước đi đến ô này là (x + y) / 3.
 |
| Những ô màu tím là những bài toán (x + y) % 3 = 0 |
Nếu (x + y) % 3 = 1: những ô trên đường chéo phụ x + y này có thể đi đến từ đường chéo phụ (x + y) % 3 = 1 ngay trước nó trong 1 bước, trừ ô (2, 2) ta đã tính kết quả sẵn, ở đường chéo phụ (x + y) % 3 = 1 đầu tiên sẽ tốn 3 bước để đến đó, do đó số bước đi đến ô này sẽ là (x + y) / 3 - 2 + 3 = (x + y) / 3 + 1 (trừ 2 là tính số bước đi từ đường chéo phụ (x + y) % 3 = 1 đầu tiên và cộng là 3 là tính số bước để đi đến đường chéo phụ đầu tiên này).
 |
| Những ô màu tím là những bài toán (x + y) % 3 = 1 |
Nếu (x + y) % 3 = 2: những ô trên đường chéo phụ x + y này có thể đi đến từ đường chéo phụ (x + y) % 3 = 2 ngay trước nó trong 1 bước, ở đường chéo phụ (x + y) % 3 = 2 đầu tiên sẽ tốn 2 để đến đó, do đó số bước đi đến ô này sẽ là (x + y) / 3 + 2.
 |
| Những ô màu tím là những bài toán (x + y) % 3 = 2 |
Tổng hợp:
if x = 1 and y = 0 then return 3
if x = 2 and y = 2 then return 4
if y = 0 or x / y ≥ 2 then
if x % 4 = 0 then return x / 2 + y % 2
if x % 4 = 1 then return x / 2 + y % 2 + 1
if x % 4 = 1 then return x / 2 - y % 2 + 1
if x % 4 = 1 then return x / 2 - y % 2 + 2
else return (x + y) / 3 + (x + y) % 3
Khi đã có các công thức này rồi, việc còn lại là brute force đi lùi quân tốt dần dần và tính d[x][y] cho tới khi nào thỏa thì ngưng. Đối với cách này có thể tăng vùng lên tới -1e6 → 1e6, -1e6 → 1e6.
Độ phức tạp O(2500)
Code:
#include <iostream>
using namespace std;
int calc(int x, int y) {
x = max(x, -x); y = max(y, -y);
if (x < y) swap(x, y);
if (x == 2 && y == 2) return 4;
if (x == 1 && y == 0) return 3;
if (!y || x / y >= 2) {
if (x % 4 == 0) return x / 2 + y % 2;
if (x % 4 == 1) return x / 2 + y % 2 + 1;
if (x % 4 == 2) return x / 2 - y % 2 + 1;
if (x % 4 == 3) return x / 2 - y % 2 + 2;
}
else return (x + y) / 3 + (x + y) % 3;
}
int main() {
int kx, ky, px, py, turn;
cin >> kx >> ky >> px >> py >> turn;
if (((kx + ky + px + py) & 1) == turn) {
cout << "NO"; return 0;
}
for (int cnt = 1 - turn; ; --px, ++cnt) {
int step = calc(kx - px, ky - py);
if (step <= cnt && (cnt - step) % 2 == 0) {
cout << "YES\n" << cnt; return 0;
}
}
}
Trong khi thi hình như hông có ra công thức này đâu :)
Nhận xét
Đăng nhận xét