POJ 1321 棋盘问题(C)回溯

Emmm,我又来 POJ 了,这题感觉比上次做的简单点。类似皇后问题。但是稍微做了一点变形,比如棋子数量是不定的。棋盘形状不在是方形等等。

题目链接:POJ 1321 棋盘问题


解题思路

基本思路:从上往下放旗子,每种情况完成后,复盘继续下一种情况。

这里讲一下,void backTrack(int left, int x) 函数。

left 表示还剩的棋子数量,显然如果 left 为 0,说明所有棋子已放完,那么方案数 solution 加 1。

如果不为 0。那么继续检查当前位置的列是否有棋子,如果无棋子,那么当前位置可以放旗子。然后继续递归,棋子数量减 1,行数加 1。如果有棋子,那么悔棋 1 步。继续下一个位置。

C代码

/**
* @author wowpH
* @date 2019-9-14 19:54:16
*/
#include<stdio.h>
#include<string.h> #define TRUE 1
#define FALSE 0 #define MAX_N 8 // 矩阵最大为8 #define BOARD TRUE // 棋盘
#define BLANK FALSE // 空白 int matrix[MAX_N][MAX_N];// 矩阵,BOARD表示棋盘,BLANK表示空白 int n, k, solution;// solution最终结果 int column[MAX_N];// 每列是否有棋子,TRUE表示有棋子,FALSE表示无棋子 void backTrack(int left, int x) {// 回溯,left表示剩余棋子,x表示当前行
if (left == 0) {// 无多余棋子
++solution; // 方案数加1
return;
} // 遍历x行及下方的棋盘
for (int i = x; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == BLANK) {// 空白
continue; // 不能放旗子
}
if (column[j] == TRUE) {// 第j列有棋子
continue; // 不能放旗子
} column[j] = TRUE; // 当前位置可以放子,设为TRUE
backTrack(left - 1, i + 1); // 回溯,棋子数减1,行数加1
column[j] = FALSE; // 复盘,设为无子
}
}
} int main() {
while (scanf("%d %d", &n, &k) && n != -1 && k != -1) {
getchar();// '\n' // 输入棋盘
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char ch = getchar();
if (ch == '.') {
matrix[i][j] = BLANK;// 空白
} else if (ch == '#') {
matrix[i][j] = BOARD;// 棋盘
}
}
getchar();// '\n'
} // 初始化
memset(column, FALSE, sizeof(column));
solution = 0; backTrack(k, 0);// 回溯 printf("%d\n", solution);
}
return 0;
}

提交结果

POJ 1321 棋盘问题(C)回溯

上一篇:poj 1321 棋盘问题 递归运算


下一篇:atitit.软件开发方法总结O6