資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告