题解 | N皇后问题

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    
    int count = 0;
    bool Isfit(vector<vector<bool>>& Pos, int n, int i, int j) {
        //检查当前(i,j)皇后与其他皇后是否有冲突；
        for (int l = 0; l < n; l++) {
            if (l == i) continue;
            if (Pos[l][j] == true) return false;
        }
        for (int k = 0; k < n; k++) {
            if (k == j) continue;
            if (Pos[i][k] == true) return false;
        }
        for(int m=1;m<n;m++){
            if(i-m>=0 && j+m<=n-1) if(Pos[i-m][j+m]==1) return false;
            if(i+m<=n-1 && j-m>=0) if(Pos[i+m][j-m]==1) return false;
            if(i+m<=n-1 && j+m<=n-1) if(Pos[i+m][j+m]==1) return false;
            if(i-m>=0 && j-m>=0) if(Pos[i-m][j-m]==1) return false;
        }
        return true;
    }

    bool IsValid(vector<vector<bool>>& Pos, int n, int i, int j) {
        if(Isfit(Pos, n, i, j)==false) {cout<<"i="<<i<<",j="<<j<<" 编号:"<<1<<"count:"<<count<<"\n";return false;}
        if(Isfit(Pos, n, i, j)==true && j==n-1) {cout<<"i="<<i<<",j="<<j<<" 编号:"<<2<<"count:"<<count<<"\n";count++;return true;}
        if(Isfit(Pos, n, i, j)==true){
            cout<<"i="<<i<<",j="<<j<<" 编号:"<<3<<"count:"<<count<<"\n";
            for(int row=0;row<n;row++){
                //指定j+1列
                Pos[row][j+1] =true;
                IsValid(Pos,n,row,j+1);
                Pos[row][j+1] =false;
                // if(IsValid(Pos,n,row,j+1)) return true;
                // else Pos[row][j+1] =false;
            }
            return false;
        }
        return false;
    }
    int Nqueen(int n) {
        // write code here
        
        vector<vector<bool>> Pos(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            Pos[i][0] = true;
            IsValid(Pos, n, i, 0);
            // if (IsValid(Pos, n, i, 0)) count++;
            Pos[i][0] = false;
        }
        return count;
    }
};