HDU-2553 N皇后问题

系统管理员 2022-06-12 20:41 126阅读 0赞

## N皇后问题 ##

[HDU - 2553 ][HDU - 2553]

在N\*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。   
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

1
    8
    5
    0

Sample Output

1
    92
    10

八皇后问题是最经典最基础的DFS问题，所有DFS的入门都是从八皇后开始。这题的题意题目里已经写的很清楚了，我们只需要不断递归搜索然后回溯即可找到解，有一点要注意的是在各大OJ上这道题好像都要打表才能过，所以AC代码如下

## `#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int tot; int N; int C[15]; int vis[3][100]; void search(int cur) { if (cur == N) tot++; else for (int i = 0; i < N; i++) { if (!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + N]) { C[cur] = i; vis[0][i] = vis[1][cur + i] = vis[2][cur - i + N] = 1; search(cur + 1);//递归搜索 vis[0][i] = vis[1][cur + i] = vis[2][cur - i + N] = 0;//这里是回溯 } } } int main() { while (scanf("%d",&N)!=EOF) { if (N == 0)//从这里开始打表 break; if (N == 10) printf("724\n"); if (N == 9) printf("352\n"); if (N == 8) printf("92\n"); if (N == 7) printf("40\n"); if (N == 6) printf("4\n"); if(N<=5) { tot = 0; memset(vis, 0, sizeof(vis)); memset(C, 0, sizeof(C)); search(0); printf("%d\n", tot); } } }`      ##

[HDU - 2553]: https://vjudge.net/problem/33634/origin

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 2553 n皇后问题（回溯）

本题用回溯法求解（采用边生成边检查的方式），当不满足条件时当前路径不再继续向下搜寻，而继续另外路径的搜寻（这样就不会枚举所有的）。通过逐行向下判断（每行一个皇后），每行都尝

灰太狼/ 2024年02月17日 19:00/ 0 赞/ 14 阅读

相关 HDU 2553 N皇后问题

N皇后问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth

青旅半醒/ 2022年10月02日 14:57/ 0 赞/ 87 阅读

相关 HDU-2553 N皇后问题

N皇后问题 [HDU - 2553 ][HDU - 2553] 在N\N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允

系统管理员/ 2022年06月12日 20:41/ 0 赞/ 127 阅读

相关 hdu-2553 N皇后（深搜）

[原题][Link 1] 思路：以列深搜，看每一行是否符合条件，注意打表，否则超时。 include<iostream> include<algorit

r囧r小猫/ 2022年06月09日 00:42/ 0 赞/ 116 阅读

相关 HDU 2553 N皇后问题 (DFS)

/题意自己看，不会度娘 include <stdio.h> include <string.h> include <math.h>

短命女/ 2022年06月08日 08:41/ 0 赞/ 118 阅读

相关 HDU N皇后问题 2553 【深搜练习】

N皇后问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

悠悠/ 2022年06月05日 09:46/ 0 赞/ 99 阅读

相关 HDU - 2553 N皇后问题 (DFS)

N皇后问题 Problem Description 在N\N的方格棋盘放置了

超、凢脫俗/ 2022年05月19日 05:37/ 0 赞/ 137 阅读

相关 N 皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包

喜欢ヅ旅行/ 2022年05月17日 04:52/ 0 赞/ 183 阅读

相关 HDU 2553 N皇后问题

原题目链接[HDU2553][] -------------------- 分类 HDU 搜索 DFS 打表 -------------------- 题意

╰+哭是因爲堅強的太久メ/ 2022年04月16日 04:59/ 0 赞/ 113 阅读

相关 n皇后问题

package test; public class Main{ static final int n=4; static int

客官°小女子只卖身不卖艺/ 2022年03月25日 06:22/ 0 赞/ 202 阅读