代码随想录算法训练营第三十四天 | LeetCode 51、37

前言

LeetCode题目：LeetCode 51、37
Takeaway：回溯算法总结，以及什么是二维回溯。

一、51

著名的N皇后问题，本质就是回溯迭代每行，for循环遍历当前行的每列，其实本质和普通的回溯没有区别，检查是否合法的时候，需要注意对角线的方向，如果递归到了最后一行+1行，说明没有冲突，将其加入答案。

class Solution {
   
public:
    vector<vector<string>> result;

    bool isValid(int row, int col, vector<string>& chessboard, int n) {
   
        //检查列
        for(int i=0; i<row; i++){
   
            if(chessboard[i][col]=='Q'){
   
                return false;
            }
        }

        //检查对角线
        int i= row-1;
        int j =col-1;
        while(i>=0 && j>=0){
   
            if(chessboard[i][j]=='Q'){
   
                return false;
            }
            i--;
            j--;
        }

        //检查对角线2，角度不一样
        i= row-1;
        j =col+1;
        while(i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32