美文网首页
【洛谷 P1219】八皇后

【洛谷 P1219】八皇后

作者: Siding | 来源:发表于2018-10-04 16:36 被阅读0次

    八皇后(题目链接)

    思路

    • 典型的深搜回溯问题

    代码

    #include <iostream>
    using namespace std;
    
    struct Point{
        int x;
        int y;
    };
    
    int N = 0;          //要放的皇后的个数 
    int num = 0;        //保存已经放下的皇后的数量 
    int ans = 0;        //保存已经找到的答案种数 
    Point q[14];        //保存已经放下的皇后的位置
    
    //判断该位置能不能放皇后 
    int check(int x, int y){
        //遍历已经放下的每一个皇后,计算是否冲突 
        for(int i = 1; i <= num; i++){
            //与第i个皇后同行的 
            if(x == q[i].x){
                return 0;
            }
            //与第i个皇后同列的 
            if(y == q[i].y){
                return 0;
            }
            //与第i个皇后同斜线的    
            if(x + y == q[i].x + q[i].y){
                return 0;
            }
            //与第i个皇后同反斜线的 
            if(x - y == q[i].x - q[i].y){
                return 0;
            }
        }
        return 1;   
    }
    
    void dfs(int x){
        //如果已经考虑完每一行 
        if(x > N){
            //并且已经放下了N个皇后 
            if(num == N){
                ans++;
                //输出前三种解 
                if(ans <= 3){
                    for(int i = 1; i <= N; i++){
                        cout << q[i].y << " ";
                    }
                    cout << endl;
                }
            }
            return;
        }
        //遍历每一行的每一个位置 
        for(int y = 1; y <= N; y++){
            //如果能够放下皇后 
            if(check(x,y) == 1){
                //已经放下的皇后数增加1 
                num++;
                //记下刚刚放下皇后的位置 
                q[num].x = x;
                q[num].y = y;
                //搜索下一行 
                dfs(x+1);
                //把放下的皇后的数目减1
                //相当于拿起当前位置的皇后,继续考虑该行的下一个位置 
                num--;
            }
        }
    }
    
    
    int main(){
        cin >> N;
        dfs(1);
        cout << ans;
    }
    

    相关文章

      网友评论

          本文标题:【洛谷 P1219】八皇后

          本文链接:https://www.haomeiwen.com/subject/qrbxaftx.html