|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
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