欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

八皇后问题(深搜与暴力方法)

程序员文章站 2022-05-24 09:34:36
...
***

## 正确答案:

***
#include<bits/stdc++.h>
using namespace std;
int count1,n,a[1000],b[1000],kn[100],su[100];
void dfs(int sum){
	if(sum==n+1){
		count1++;
		if(count1>3)
		return;
		for(int i=1;i<=n;i++){
			cout<<su[i]<<" ";	
		}
		cout<<endl;
		return;
	}
	for(int j=1;j<=n;j++){
		if(!kn[j]&&!b[j+sum]&&!a[sum-j+n]){
/*本题精华:通过对数组元素的名称进行操作再对元素值操作可以实现查询(具有某一特性的)位置是否被占用。*/
			kn[j]=b[j+sum]=a[sum-j+n]=1;
			su[sum]=j;
			dfs(sum+1);
			kn[j]=b[j+sum]=a[sum-j+n]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<count1;
	return 0;
	
} 
***错误示范:***
#include<bits/stdc++.h>
using namespace std;
struct  node
{
    int x,y;	
};
int item,x,y;
int flag=1;

void pai( int end ,node a[],int m)
{
    if(m==end)
    {
        for(int i=0;i<end;i++)
    {
        x=a[i].x-a[i].y;
        y=a[i].x+a[i].y;
        for(int j=i+1;j<end;j++){
            if((a[j].x-a[j].y)==x||(a[j].x+a[j].y)==y)
            return;
        }
            }
    if(item<3)
    for(int i=0;i<end;i++)
    cout<<a[i].x<<" ";
    if(item<3)
    cout<<endl;
        item++;
        return;
    }

    for(int i=1;i<=end;i++)
    {
    flag=1;
        a[m].x=i;
    for(int j=0;j<=m;j++)
    {
    for(int k=j+1;k<=m;k++)
    {
        if(a[j].x==a[k].x)
        {
            flag=0;
            break;
        }
    }
        if(flag==0)
        break;}
        if(flag==0)
        continue;
        pai( end, a, m+1);
}

}

int main(){
    int n,m=0;
    cin>>n;
    node a[n];
    for(int i=1;i<=n;i++)
    a[i-1].y=i;
    pai(n,a,m);
    cout<<item<<endl;
    return 0;
}
相关标签: 深度搜索

上一篇: 18276 走迷宫

下一篇: js 取参数