HDU-2553,N皇后问题(DFS+回溯)

简介: HDU-2553,N皇后问题(DFS+回溯)

Problem Description:


在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。

你的任务是,对于给定的N,求出有多少种合法的放置方法。


Input:


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


Output:


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


Sample Input:



1

8

5

0


Sample Output:


1

92

10


AC Code:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 15
int n,ans,pos[N],a[N];
int place(int k)
{
  int i;
  for(int i=1;i<k;i++)
    if((abs(k-i)==abs(pos[k]-pos[i]))||pos[k]==pos[i])
    //i表示皇后所在的行数,pos[i]表示所在的列数,
    //所以前面那个条件用来判断两个皇后是否在对角线上,后面用来判断是否在同一列上。
    //行数不需要判断,因为他们本身的i就代表的是行数 
      return 0;
  return 1;
}
void dfs(int t)
{
  if(t>n)//皇后个数大于需要摆放的数量 
    ans++;//方案数+1 
  else
  {
    for(int i=1;i<=n;i++)
    {
      pos[t]=i;//第t个皇后所放置的列数 
      if(place(t))//判断是否能放 
        dfs(t+1);//能的话,继续放下一个 
    }
  }
}
int main()
{
  for(int j=1;j<=10;j++)
  {
    n=j;//表示有几个皇后 
    ans=0;//方案数每次都要清零 
    dfs(1);//每次都要从第一个皇后开始 
    a[j]=ans;
  }
  while(cin>>n)//此时已打表完毕 
  {
    if(!n)
      break;
    cout<<a[n]<<endl;//输出对应结果即可 
  }
  return 0;
}
相关文章
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
157 0
|
机器学习/深度学习 存储 算法
【DFS经典例题】2n皇后问题
【DFS经典例题】2n皇后问题
84 0
|
8月前
|
存储 人工智能 BI
【每日一题Day216】LC1377 T 秒后青蛙的位置 | BFS DFS
【每日一题Day216】LC1377 T 秒后青蛙的位置 | BFS DFS
61 0
|
存储 容器
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
166 0
|
定位技术
UPC——帕琪的药园(dfs或并查集)
UPC——帕琪的药园(dfs或并查集)
88 0
|
定位技术 C++
HDU-1253,胜利大逃亡(DFS)
HDU-1253,胜利大逃亡(DFS)
洛谷P1331-海战(简单的DFS)
洛谷P1331-海战(简单的DFS)
|
机器学习/深度学习
POJ-1321,棋盘问题(DFS)
POJ-1321,棋盘问题(DFS)
|
存储 数据可视化
回溯求解N皇后问题
前期尝试过8皇后问题,虽然最后完成了求解,但过程其实是比较懵圈的
114 0