N皇后問題(DFS)
N皇后問題
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3579 Accepted Submission(s): 1654
Problem Description
N*Nの四角い碁盤には、互いに攻撃しないようにN個の皇后が置かれている(すなわち、任意の2個の皇后は同じ列にいてはならず、同じ列にいても、碁盤の枠と45角の斜線にいてはならない.
あなたの任務は、与えられたNに対して、どれだけの合法的な配置方法があるかを求めることです.
Input
いくつかの行があり、行ごとに正の整数N≦10で、碁盤と皇后の数を表します.N=0の場合、終了を表します.
Output
いくつかの行があり、各行に正の整数があり、入力行に対応する皇后の異なる配置数を表します.
Sample Input
Sample Output
Author
cgf
Source
2008 HZNU Programming Contest
Recommend
lcy
DFS+メーター
検索コード:
そして配列で保存して...わかりました
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3579 Accepted Submission(s): 1654
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
Author
cgf
Source
2008 HZNU Programming Contest
Recommend
lcy
DFS+メーター
検索コード:
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXI 2147483647
#define MAXL 9223372036854775807
#define dg(i) cout << "*" << i << endl;
using namespace std;
int n, q[11]; // , i q[i]
bool check(int r)
{
int i;
for(i = 1; i < r; i++)
if(q[i] == q[r])
return false;
for(i = r - 1; i > 0; i--)
if(q[i] == q[r] - (r - i) || q[i] == q[r] + r - i)
return false;
return true;
}
//r
int DFS(int r)
{
if(r == n + 1) return 1;
int cnt = 0;
for(q[r] = 1; q[r] <= n; q[r]++)
{
if(check(r))
{
cnt += DFS(r + 1);
}
}
return cnt;
}
int main()
{
int ans;
while(scanf("%d", &n) && n)
{
memset(q, 0, sizeof(q));
ans = 0;
for(q[1] = 1; q[1] <= n; q[1]++)
{
ans += DFS(2);
}
printf("%d
", ans);
}
return 0;
}
そして配列で保存して...わかりました