hdu2553.MD

日期 2021 / 10 / 21

题目

[题目链接]https://acm.dingbacode.com/showproblem.php?pid=2553

N皇后问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 63399 Accepted Submission(s): 25928

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

解题思路

N皇后问题是dfs类型的经典题目,意思是在n*n的方阵中摆棋子使其不能在同一行同一列以及同一对角线,这里我利用的 是一个数组b来判断每一行的第几个是否被用过,dfs里面的m可以理解为第几行，那么b[m]就是那一行的第几个,相当于 m代表的是x，b[m]代表的是y,那么怎么去判断两点是否在呈45度的斜线上,我的想法是如果两个点在45度斜线,上假设 某一点是(x,y)那么和它呈45度的点是(x + 1, y - 1)可以看出他们的坐标之差的绝对值一定一样,对于是否同一行同 一列则直接判断b[m]是否等于b[i],在所以根据这些就能解出题目,还有一点就是这个题需要我们先去打表计算,不然会 超时,毕竟是多组输入。

代码演示

#include <bits/stdc++.h>

#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 0, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e6 + 10;
using namespace std;

int a[11], b[11];
int cnt, n, t;

bool check(int m) {
  for (int i = 1; i < m; i++) {
    if (abs(m - i) == abs(b[m] - b[i]) || b[m] == b[i]) {
      return false;
    }
  }
  return true;
}

void dfs(int m) {
  if (m > n) {
    cnt++;
  }
  for (int i = 1; i <= n; i++) {
    b[m] = i;
    if (check(m)) {  // b[m]检查这一行的第m个是否被占用过
      dfs(m + 1);
    }
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  for (int i = 1; i <= 10; i++) {
    n = i;
    cnt = 0;
    dfs(1);
    a[i] = cnt;
  }
  while (cin >> t && t) {
    cout << a[t] << endl;
  }
  return 0;
}