N皇后 II（需要注意的地方很多，主要看注释）（不同的回溯法）

 

需要注意的地方很多，主要看注释：

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

 

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

 

提示：

    皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。（引用自 百度百科 - 皇后 ）

即：

       对角线既包括主对角线，也包括副对角线。

class Solution {
public:
    int totalNQueens(int n) {
        //走走走 不行再回来，就叫回溯法。
        //回溯法除分割字符串之外的又一应用。
        //回溯法的经典格式。
        //主函数只调用backtracing()，只需要在之前做一些初始化。
        int dp[1000][1000];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                dp[i][j]=0;
            }
        }
        //上面相当于middle，一般用到回溯都有很多中解决方案。有个middle，有个res。middle在终止条件进入res,这里只要数量，所以只要在终止条件处count++就可以了。（但要传count）
        int count=0;
        backtracing(0,dp,n,count);//每一行都有，每次往后循环列，但每次行固定。从第0行开始。因为不设返回值，主函数里定义的变量count就记录了result.
        return count;
        //上面还有函数传的是形参还是实参的问题。传的到底是形还是实参在调用的这边是看不出来的，主要看backtracing函数，在声明里面加的是'&'才管用。众所周知，传形参的话，count是永远等于0的，算对了也是等于0的。


    }
    //我觉得我写的没毛病啊！
    void backtracing(int row,int dp[][1000],int n,int &count)//int dp[][],int n是一起的，传数组就是这么麻烦
    {
        if(row==n)
        {
            count++;
            //cout<<count<<endl;
            
            return;
        }
        for(int col=0;col<n;col++)//col=0开始，不用从col=row开始，因为它可以用之前的列，和分割字符串不一样。 能不能用之前相同的是重点——主要也是看含义，字符串end的话肯定不能比start大，但是这里col和row就没有这种关系。
        {
            if(isValid(row,col,dp,n))
            {
                dp[row][col]=1;
                //cout<<count<<endl;
                backtracing(row+1,dp,n,count);//所以这里也不一样了。不用end+1.(因为之前每次end=start所以采用end+1来一样代替的，实际上是row(start)+1.)
                dp[row][col]=0;
            }
        }
    }
    //有个判断条件
    //判断是否在同一条斜线上可通过当前将要摆放'Q'的位置和其他已摆放‘Q’的位置横坐标之差和纵坐标之差的绝对值是否相等来判断。
    bool  isValid(int x,int y,int dp[][1000],int n)//int dp[][],int n是一起的，传数组就是这么麻烦
    {
       //直接遍历所有找到已有的位置。
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(dp[i][j]==1)
                {
                    if(i==x) return false;
                    if(j==y) return false;
                    if(abs(i-x)==abs(j-y)) return false;//不光是主对角线，还有可能是副对角线。副对角线的话符号不同。
                }
            }
        }
        return true;
        // for(int j=0;j<n;j++)
       // {
       //     if(dp[xIndex][j]==1) return false;
       // }
       // for(int i=0;i<n;i++)
       // {
       //     if(dp[i][yIndex]==1) return false;
       // }
    }
};