Trong bài toán này, cho bàn cờ m*n với các ô đã chiếm đánh dấu bằng 1 (board[i][j] = 1 có quân cờ). Cho vị trí bắt đầu. Nhiệm vụ tìm tổng số nước đi có thể của quân Mã, giả sử tất cả quân cờ cùng màu (không tấn công nhau).
Quân Mã di chuyển đặc biệt:
Hai ô ngang và một ô dọc.
Hai ô dọc và một ô ngang.
Ví dụ minh họa:
Đầu vào -
board[][] = {
{ 0, 1, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 0, 1 }
};
Vị trí: (1,1)
Kết quả - 4
Để giải bài toán, tìm các nước đi hợp lệ trong 8 nước đi khả dĩ của Mã. Nước đi hợp lệ nếu nằm trong bàn cờ và ô đó không bị chiếm.
Lưu trữ 8 nước đi khả dĩ, kiểm tra tính hợp lệ của từng nước, đếm số nước hợp lệ.
Chương trình minh họa
#include <bits/stdc++.h>
#define N 8
#define M 8
using namespace std;
int countPossibleMoves(int mat[N][M], int p, int q) {
int Xmoves[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int Ymoves[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int count = 0;
for (int i = 0; i < 8; i++) {
int x = p + Xmoves[i];
int y = q + Ymoves[i];
if (x >= 0 && y >= 0 && x < N && y < M && mat[x][y] == 0)
count++;
}
return count;
}
int main() {
int mat[N][M] = {
{ 0, 1, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 0, 1 }
};
int position[2] = {1, 1};
cout << "Tổng số nước đi có thể của Mã từ vị trí (" << position[0] << " , " << position[1] << ") là: ";
cout << countPossibleMoves(mat, position[0], position[1]);
return 0;
}
Kết quả
Tổng số nước đi có thể của Mã từ vị trí (1 , 1) là: 4