题解 | N皇后问题

// 学了这么长时间还是啥也不是
// 那就总结一下这次二刷的问题把
// 1.定义了二维的容器或数组以后，一定要动态分配或等效分配每一行的内存
// 2.本题中检查棋盘空格是否安全，应该从每一个方格出发直到边界
// 3.传递大小大于指针的参数时，一定！！！一定！！！一定！！！
// 要采用引用的方式调用！！！

#include <vector>

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 the n
     * @return int整型
     */
    bool is_safe(int row,int col,std::vector<std::vector<bool>>&board,int n)
    {
        for (int i = 0;i < row;i++)
        {
            if (board[i][col] == true) return false;
        }

        // 注意！！！这里是从确定位置出发往不确定位置走！！！
        for (int i = row-1,j = col-1;i >= 0&&j >= 0;i--,j--)
        {
            if (board[i][j] == true)   return false;
        }
        for (int i = row-1,j = col+1;i >=0&&j <n;i--,j++)
        {
            if (board[i][j] == true)   return false;
        }
        return true;
    }
    void recursion(std::vector<std::vector<bool>>&board,int row,int n,int &count)
    {
        if (row == n)
        {
            count++;
            return;
        }
        for (int i = 0;i < n;i++)
        {
            if (is_safe(row,i,board,n))
            {
                board[row][i] = true;
                recursion(board,row+1,n,count);
                board[row][i] = false;
            }
        }
    }
    int Nqueen(int n)
    {
        int count = 0;
        std::vector<std::vector<bool>>board(n,std::vector<bool>(n,false));
        
        // Initialize all the element as false
        recursion(board,0,n,count);
        return count;
    }
};