数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中放置K个骑士，使其互不攻击
在这个问题中，我们得到三个整数值K、N、M。我们的任务是在NxM棋盘上放置K个骑士，使得任何两个骑士都不互相攻击。可能存在0个有效方案，也可能存在多个有效方案。你需要打印所有有效的方案。
骑士是国际象棋棋子，它先向前移动两格，然后向左或向右移动一格。它可以向棋盘上的任何方向移动。
攻击是指当一个棋子可以在一次有效移动中到达另一个棋子的位置。
让我们举个例子来理解这个问题：
输入 − M = 3, N = 3, K = 5
输出 −
K A K A K A K A K A K A K K K A K A
为了解决这个问题，我们将一个接一个地将骑士放置在每一行，逐列放置。并在每次放置后检查哪些位置受到了攻击。放置骑士时，我们将检查它是否安全。如果安全，我们将放置它，然后移动到下一个位置。我们将使用回溯法，以便获得所有可能的方案，为此，我们将为回溯在每次放置骑士后创建一个新的棋盘。这就是我们将使用回溯法获得所有可能解的方法。
示例
演示我们解决方案的程序：
#include <iostream>
using namespace std;
int m, n, k, count = 0;
void displayPositions(char** board){
cout<<endl;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout<<board[i][j]<<"\t";
}
cout<<endl;
}
}
void canattack(int i, int j, char a,
char** board){
if ((i + 2) < m && (j - 1) >= 0) {
board[i + 2][j - 1] = a;
}
if ((i - 2) >= 0 && (j - 1) >= 0) {
board[i - 2][j - 1] = a;
}
if ((i + 2) < m && (j + 1)< n) {
board[i + 2][j + 1] = a;
}
if ((i - 2) >= 0 && (j + 1) < n) {
board[i - 2][j + 1] = a;
}
if ((i + 1) < m && (j + 2) <n) {
board[i + 1][j + 2] = a;
}
if ((i - 1) >= 0 && (j + 2) < n) {
board[i - 1][j + 2] = a;
}
if ((i + 1) < m && (j - 2) >= 0) {
board[i + 1][j - 2] = a;
}
if ((i - 1) >= 0 && (j - 2) >= 0) {
board[i - 1][j - 2] = a;
}
}
bool canPlace(int i, int j, char** board){
if (board[i][j] == '_')
return true;
else
return false;
}
void place(int i, int j, char k, char a,
char** board, char** new_board){
for (int y = 0; y < m; y++) {
for (int z = 0; z < n; z++) {
new_board[y][z] = board[y][z];
}
}
new_board[i][j] = k;
canattack(i, j, a, new_board);
}
void placeKnights(int k, int sti, int stj, char** board){
if (k == 0) {
displayPositions(board);
count++;
} else {
for (int i = sti; i < m; i++) {
for (int j = stj; j < n; j++) {
if (canPlace(i, j, board)) {
char** new_board = new char*[m];
for (int x = 0; x < m; x++) {
new_board[x] = new char[n];
}
place(i, j, 'K', 'A', board, new_board);
placeKnights(k - 1, i, j, new_board);
}
}
stj = 0;
}
}
}
int main() {
m = 3, n = 3, k = 5;
char** board = new char*[m];
for (int i = 0; i < m; i++)
board[i] = new char[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
board[i][j] = '_';
}
cout<<"The ways in which "<<k<<" knights can be placed in "<<m<<"x"<<n<<" chessboard are :\n";
placeKnights(k, 0, 0, board);
return 0;
}输出
The ways in which 5 knights can be placed in 3x3 chessboard are : K A K A K A K A K A K A K K K A K A
在这里，我们用K标记骑士的位置，用A标记骑士攻击到的位置。
更新于：2020年4月17日
441 次浏览
广告