## Đảm bảo Input
Nếu bạn đang lo lắng về Input (ví dụ: Nếu trong trường hợp $n=2$ và $m=2$ thì quân mã sẽ đi như thế nào?). Thì bạn không cần phải lo vì bài sẽ đảm bảo Input cho các bạn là sẽ có cách đi
## Cách di chuyển
Bạn có thể tham khảo cách di chuyển ở đây: [Wikipedia](https://vi.wikipedia.org/wiki/Mã_(cờ_vua))
Từ cách di chuyển của quân Mã, ta có thể tính được vị trí của quân Mã trong các lần di chuyển.
Cụ thể, nếu quân Mã đang ở vị trí $(x,y)$ thì nó có thể di chuyển tới các vị trí:
- $(x+1,y+2); (x-1,y+2); (x-2;y+1); (x+2,y+1)$
- $(x-2;y-1); (x+2;y-1); (x-1;y-2); (x+1;y-2)$
## Thuật đệ quy
Trong thuật đệ quy của bài này, ta sẽ xét 3 giá trị chính, đầu tiên là $cnt$, là biến để đếm số ô mà quân Mã đã đi qua. Tiếp theo là hai biến $x,y$ để tượng trưng cho việc quân Mã đang đứng ở vị trí $(x,y)$ trên bàn cờ
Ta thực hiện như sau:
- Tạo hai mảng dx và dy lưu lại các cách di chuyển của quân Mã
- Ta gọi rec(cnt+1,x,y). Ý nghĩa: Tìm vị trí thứ cnt+1 tiếp theo mà quân Mã khi đứng ở vị trí $(x,y)$ có thể đến
- Ta xét tất cả các cách di chuyển bằng cách lấy các phần tử dx[i] và dy[i].
- Gọi nx là vị trí trên hàng ngang mới của quân Mã (nx=x+dx[i]), còn ny là vị trí trên cột dọc (ny=y+dy[i])
- Lúc này ta cần kiểm tra tính đúng đắn của vị trí tiếp theo. Nếu vị trí đó là âm hoặc vượt quá độ lớn của bàn cờ $(n\times m)$ thì sẽ bỏ qua.
- Nếu vị trí đó có tồn tại và quân Mã chưa đến đây trước đó thì ta sẽ đánh dấu ô này là ô thứ cnt+1, đồng thời gọi đệ quy cho ô này. Sau khi gọi đệ quy thì ta đặt lại ô bằng 0 để quay lui và kiểm tra tiếp các vị trí có thể đến còn lại
## Kết quả
Thuật đệ quy sẽ gọi đến tất cả các vị trí có thể đi tới của quân Mã trong tất cả các trường hợp. Khi đệ quy gọi đến vị trí thứ $n \times m$ (tức là đây là vị trí cuối mà quân Mã có thể tới, với tất cả các ô còn lại đã được đi qua), ta sẽ in ra bàn cờ đã đánh dấu trước đó.
**LƯU Ý**: Trong hàm đệ quy, khi cnt==$n \times m$ thì ta sẽ sử dụng exit(0); để kết thúc việc xét (vì ta chỉ cần 1 cách di chuyển là được, nếu dùng return ; thì đệ quy sẽ tiếp tục kiểm tra các cách đi còn lại và rất có thể sẽ còn những cách đi khác nên nó sẽ tiếp tục in ra)
## Code tham khảo
```cpp
#include <bits/stdc++.h>
using namespace std;
#define TASK ""
#define ll long long
int n,m;
int a[8][8];
int dx[]={1,-1,-2,2,-2,2,-1,1};
int dy[]={2,2,1,1,-1,-1,-2,-2};
void rec(int cnt, int x, int y) {
if (cnt==n*m) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++)
cout << a[i][j] << " ";
cout << '\n';
}
exit(0);
}
for (int i=0;i<8;i++) {
int nx=x+dx[i],ny=y+dy[i];
if (nx>0 && nx<=n && ny>0 && ny<=m && a[nx][ny]==0) {
a[nx][ny]=cnt+1;
rec(cnt+1,nx,ny);
a[nx][ny]=0;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(TASK".inp","r")) {
freopen(TASK".inp","r",stdin);
freopen(TASK".out","w",stdout);
}
cin >> n >> m;
memset(a,0,sizeof(a));
a[1][1]=1;
rec(1,1,1);
}
```
Horizon
Created at
1 likes