Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng vị trí có thể đến được bởi Mã (Knight) biến thể.
Cho bàn cờ 8x8. Nhiệm vụ là tìm số vị trí Mã biến thể có thể đến sau số bước cho trước.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void findSteps(int cr, int cc, int curr, int board_size, int steps, int* visited) {
if(cr >= board_size || cr < 0 || cc >= board_size || cc < 0 || curr > steps)
return;
if(curr == steps) {
*((visited + cr * board_size) + cc) = 1;
return;
}
// 12 nước đi của Mã biến thể
findSteps(cr - 2, cc - 1, curr + 1, board_size, steps, visited);
findSteps(cr - 2, cc + 1, curr + 1, board_size, steps, visited);
findSteps(cr - 1, cc - 2, curr + 1, board_size, steps, visited);
findSteps(cr - 1, cc - 1, curr + 1, board_size, steps, visited);
findSteps(cr - 1, cc + 1, curr + 1, board_size, steps, visited);
findSteps(cr - 1, cc + 2, curr + 1, board_size, steps, visited);
findSteps(cr + 1, cc - 2, curr + 1, board_size, steps, visited);
findSteps(cr + 1, cc - 1, curr + 1, board_size, steps, visited);
findSteps(cr + 1, cc + 1, curr + 1, board_size, steps, visited);
findSteps(cr + 1, cc + 2, curr + 1, board_size, steps, visited);
findSteps(cr + 2, cc - 1, curr + 1, board_size, steps, visited);
findSteps(cr + 2, cc + 1, curr + 1, board_size, steps, visited);
}
int countSteps(int cr, int cc, int board_size, int steps) {
vector<vector<int>> visited(board_size, vector<int>(board_size, 0));
findSteps(cr, cc, 0, board_size, steps, &visited[0][0]);
int answer = 0;
for(int i = 0; i < board_size; i++)
for(int j = 0; j < board_size; j++)
if(visited[i][j] == 1) answer++;
return answer;
}
int main() {
int board_size = 8, steps = 1;
int cr = 4, cc = 4;
cout << countSteps(cr, cc, board_size, steps);
return 0;
}
Kết quả
12