马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
快两年没有来鱼C学编程了，当初看小甲鱼的C语言和汇编教程（汇编基本全忘了。。。），
不过经常过来也就是打打酱油，今天微博看到小甲鱼的数据结构八皇后教程。
想起当初学算法的时候，没有完成这道经典题目，于是就试着写了个。
在小甲鱼的代码基础上对检测冲突和棋盘的空间复杂度做了点优化。。。
很久没有用C/C++写代码，大一大二学的是C++
去年升大三开始学校学的是Java，很久没用指针，
不知道写的好不好，轻拍O(∩_∩)O~#include <stdio.h>
#define CHESS_ROW 8 //棋盘行数
#define CHESS_COLUMN 8 //棋盘列数
//清除row+1行的棋子
void clearRow(int row, int ch[][CHESS_COLUMN]) {
int j;
for (j = 0; j < CHESS_COLUMN; j++)
ch[row][j] = 0;
}
//判断是否有冲突，有冲突返回1，没有返回0
/*
* 由于棋子是由上往下一行行排列的，
* 所以没有必要判断下半部分的棋盘
* 是否有冲突（还没有摆棋子），
* 只需要判断上半列，左上，右上三个方向。
* 即每次判断上一行的(row-1,col),(row-1,col-1)和(row-1,col+1)
* 三个位置即可
*/
int isConflict(const int row, const int col, const int ch[][CHESS_COLUMN]) {
int i;
int offset = 1; //用于判断左右两边的偏移量
for (i = row - 1; i >= 0; i--, offset++) {
if ( ch[i][col] != 0) {
return 1; //上半列有冲突
}
if ( (col - offset) >= 0) {
if ( ch[i][col - offset] != 0) { //判断是否越界
return 1; //左上有冲突
}
}
if ( (col + offset) < CHESS_COLUMN) { //判断是否越界
if ( ch[i][col + offset] != 0) {
return 1; //右上有冲突
}
}
}
return 0; //没有冲突返回0
}
//打印棋盘
void printChess(int ch[][CHESS_COLUMN] ) {
int i, j;
static int count = 1;
printf("第%d种情况：\n", count);
for (i = 0; i < CHESS_ROW; i++) {
for (j = 0; j < CHESS_COLUMN; j++) {
printf("%d ",ch[i][j]);
}
printf("\n");
}
printf("\n");
count++;
}
/*
* 八皇后递归算法，只使用了一个棋盘。
* 每次摆放到该行的最后一列时，
* 在返回上一行前先清空上一行上面
* 摆放的棋子。则不需要每次调换都
* 生成棋盘记录当前棋盘状况。
*/
void eightQueen(const int row, int ch[][CHESS_COLUMN]) {
int j;
if (row == 8) { //第八行完成，打印棋盘
printChess(ch);
clearRow(row - 1, ch); //清空最后一行，以便下一轮计算
return;
}
for (j = 0; j < CHESS_COLUMN; j++) {
if ( !isConflict(row, j, ch)) { //检测没有冲突，递归调用
ch[row][j] = 1;
eightQueen(row + 1, ch);
}
}
if (row > 0) { //没有到首行，则清空上一行
clearRow(row - 1, ch);
}
}
int main() {
int chess[CHESS_ROW][CHESS_COLUMN];
int i, j;
//初始化棋盘
for (i = 0; i < CHESS_ROW; i++) {
for (j = 0; j < CHESS_COLUMN; j++) {
chess[i][j] = 0;
}
}
eightQueen(0, chess);
return 0;
}
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2013-3-9 22:10:38
置顶卡
千斤顶
显身卡
发表于 2013-3-10 00:00:56