程序員面試題精選100題(58)-八皇后問題

時間:2019-09-22 編輯:范文亭
    // 程序員面試題精選100題(58)-八皇后問題.cpp : 定義控制臺應用程序的入口點。
    //
    
    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    static int sum=0;
    void swap(int &a,int &b)
    {
        int temp;
        temp=a;
        a=b;
        b=temp;
    }
    bool isqueen(int *arr,int n)
    {
        bool flag=true;
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<n;j++)
            {
                if (i!=j)
                {
                    if (i-j==arr[i]-arr[j]||i-j==arr[j]-arr[i])
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    void permution(int *arr,int i,int n)
    {
        if (i==n-1)
        {
            if (isqueen(arr,n))
            {
                sum++;
                for (int j=0;j<n;j++)
                {
                    cout<<arr[j]<<" ";
                }
                cout<<endl;
            }
        }
        else
        {
            permution(arr,i+1,n);
            for (int k=i+1;k<n;k++)
            {
                swap(arr[i],arr[k]);
                permution(arr,i+1,n);
                swap(arr[i],arr[k]);
            }
        }
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
        int arr[]={0,1,2,3,4,5,6,7};
        permution(arr,0,8);
        cout<<"sum is "<<sum<<endl;
        system("pause");
        return 0;
    }

記得兩三年前在林大的820自習室花了一天的時間做這道題,現在依然是看答案后才想出來。這題關鍵一是確定了用一元數組的數據結構后。二是采用排列的方式。三是如何判定符合條件
本文已影響
相關文章
大亨pk10计划苹果版