八皇后4

admin

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
//m数组长度10就够了，总共8*8格 
int a[10][10]={0},m[100]={0};//a[10]使用状态  m[10]排列组合
int sum=0;
int t=0;
void print()
{
        printf("%d.\n",++t);
        for (int i=1;i<=8;i++)
        {
                for (int j=1;j<=8;j++)
                        printf("%d ",a[j][i]);//a[i][j]，a[j][i]其实也没什么问题，就是行列反了 
                printf("\n");
        }
        printf("\n");
}
//check函数参数可变更为(int x,int y)
//避免使用到m[x]，因为check后才决定是否要将y赋值给m[x] 
bool check(int x)
{
        for (int i = 1; i < x; i++)
        if (m[x] == m[i] || abs(m[i] - m[x]) == x - i)return false;
        return true;
}
void dfs(int x)
{
        //结果输出放在这里不太合适，虽然结果是对的
        //放在这里结果输出后还会继续向下运行
        //在check函数中判定x[9]数据不能使用停止，不如放在下面 
        if (x>=9)print();
        for (int y=1;y<=8;y++)
        {
                //在x行y列放一枚棋子，该位置在下次循环中会被覆盖，
                //所以不回溯也没什么影响，但最好放在if语句里
                //满足可放置棋子条件时再放置 ，而不是先放置再判断
                //是不是为了check函数要用到m[x]值，所以才才提前赋值？可以在check函数中增加y参数以解决 
                m[x]=y;
                if (a[x][y]!=1&&check(x))
                {
                        a[x][y]=1;
                        //这里缺少一段，棋子布满时输出结果，你的结果输出函数print放在了程序开头部分，不太合适
                        //if(x==8) print();
                        //else dfs(x+1);
                        dfs(x+1);
                        a[x][y]=0;
                }
        }        
}


void bahuanghou()
{
        dfs(1);
}
int main()
{
        bahuanghou();
        return 0;
}