华为OJ：N皇后

悠悠 2022-08-20 04:11 174阅读 0赞

#include <math.h>
    #include <stdlib.h>
    #include <string.h>
    #include "OJ.h"
    
    /*
    功能: 求解放置8皇后方案的个数。
    输入：
    无
    返回：
    int：放置8皇后方案的个数
    */
    int* gp_arr = NULL;
    #define INITNUM -100
    
    /*对棋盘进行初始化*/
    void init(int queue)
    {
    	int i = 0;
    	for (i = 0; i < queue; i++)
    	{
    		/*初始化为-1*/
    		gp_arr[i] = INITNUM;
    	}
    }
    
    /*判断该位置是否可以放置皇后
    返回值： 0 不可以放置
    		1 可以放置
    */
    int valid(int row, int col, int queue)
    {
    	int i = 0;
    	for (i = 0; i < queue; i++)
    	{
    		/*判断列冲突和斜线上的冲突*/
    		if (gp_arr[i] == col || abs(i - row) == abs(gp_arr[i] - col))
    		{
    			return 0;
    		}
    	}
    
    	return 1;
    }
    int PlaceQueenMethodNum(int queue)
    {
    	/*在这里实现功能*/
    	int n = 0;
    	int i = 0, j = 0;
    	int count = 0;
    
    	/*给棋盘分配空间*/
    	gp_arr = (int*)malloc(sizeof(int) * queue);
    	memset(gp_arr, 0, sizeof(int) * queue);
    	
    	/*初始化这块内存*/
    	init(queue);
    
    	while (i < queue)
    	{
    		while (j < queue)
    		{
    			/*如果该位置可以放置皇后*/
    			if (valid(i, j, queue) == 1)
    			{
    				gp_arr[i] = j;
    				j = 0;
    				break;
    			}
    			else
    			{
    				j++;
    			}
    		}
    
    		/*第i行没有找到可以放置皇后的位置*/
    		if (gp_arr[i] == INITNUM)
    		{
    			if (i == 0)
    			{
    				break;
    			}
    			else
    			{
    				i--;
    				j = gp_arr[i] + 1;
    				gp_arr[i] = INITNUM;
    				continue;
    			}
    		}
    
    		/*最后一行找到了一个皇后位置，说明找到了一个结果*/
    		if (i == queue - 1)
    		{
    			count++;
    			j = gp_arr[i] + 1;
    			gp_arr[i] = INITNUM;
    			continue;
    		}
    
    		i++;
    	}
    
    	free(gp_arr);
    
    	return count;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关八皇后

八皇后问题介绍八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不

ゝ一世哀愁。/ 2022年12月24日 12:57/ 0 赞/ 123 阅读

相关皇后问题

问题 > 国际象棋中的皇后，可以横向、纵向、斜向移动。如何在一个NXN的棋盘上放置N个皇后，使得任意两个皇后都不在同一条横线、竖线、斜线方向上？举个栗子，下图的绿色格

Bertha 。/ 2022年12月06日 12:52/ 0 赞/ 179 阅读

相关八皇后

八皇后求解思路可以将八皇后看成全排列问题，因为每次都是在某一行选择某个位置，所以不需要考虑行的问题。每次只需要求出当前行的棋子所在列。所以可以化为全排列问

左手的ㄟ右手/ 2022年10月01日 11:44/ 0 赞/ 172 阅读

相关 N 皇后！

提到回溯算法那肯定离不开 n 皇后这道算法题，它实在是太经典了。所谓 n 皇后问题，指的是如何将 `n` 个皇后放置在 `n×n` 的棋盘上，并且使皇后彼此之间不能相互攻

快来打我*/ 2022年09月12日 07:51/ 0 赞/ 289 阅读

相关八皇后

/ Queen 八皇后问题：递归实现 1. 从第一行开始递归 2. 然后枚举当前行中的每一列， 3. 如果可以

r囧r小猫/ 2022年08月24日 14:25/ 0 赞/ 186 阅读

相关华为OJ：N皇后

include <math.h> include <stdlib.h> include <string.h> include "OJ.h"

悠悠/ 2022年08月20日 04:11/ 0 赞/ 175 阅读

相关八皇后

八皇后问题是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇

女爷i/ 2022年07月29日 10:52/ 0 赞/ 207 阅读

相关八皇后

package 搜索; import java.io.BufferedReader; import java.io.IOException;

一时失言乱红尘/ 2022年07月12日 12:14/ 0 赞/ 194 阅读

相关数据结构：八皇后、N皇后

八皇后： include <stdio.h> include <stdlib.h> include <math.h> include <alg

￡神魔★判官ぃ/ 2022年05月31日 14:48/ 0 赞/ 216 阅读

相关皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横

绝地灬酷狼/ 2022年04月13日 12:28/ 0 赞/ 224 阅读