三个 hard, 很夸张

332. 重新安排行程

最后结束的是死胡同点，从死胡同往后回溯。再反转下答案。

class Solution {
public:
    // 多了一个入度的是死胡同
    vector<string> res;
    unordered_map<string, priority_queue<string, vector<string>, greater<string>>> pq;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto &it : tickets)
            pq[it[0]].push(it[1]);
        dfs("JFK");
        reverse(res.begin(), res.end());
        return res;
    }

    void dfs(const string& s)
    {
        while (pq.count(s) && pq[s].size() > 0)
        {
            string t = pq[s].top();
            pq[s].pop();
            dfs(t);
        }
        res.push_back(s); // 让终点第一个进答案, 从终点往上回溯
    }
};

51. N 皇后

剪枝的dfs

class Solution {
public:
    vector<string> grid;
    vector<vector<string>> res;
    int n;
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        grid = vector<string>(n, string(n, '.'));
        dfs(0);
        return res;
    }

    // 行标
    void dfs(int u)
    {
        // 答案
        if (u == n)
        {
            res.push_back(grid);
            return;
        }

        // 将第u行的所有下标尝试变Q
        for (int i = 0; i < n; i ++)
        {
            grid[u][i] = 'Q';
            if (check(u, i))
            {
                dfs(u + 1);
            }
            grid[u][i] = '.';
        }
    }

    // 判断当前的grid是否满足条件  新加的Q下标为(x, y)
    bool check(int x, int y)
    {
        // 列
        for (int i = 0; i < x; i ++)
            if (grid[i][y] == 'Q')
                return false;

        // 正斜 只用检查上面的
        for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i --, j --)
            if (grid[i][j] == 'Q')
                return false;

        // 反斜 只用检查上面的
        for (int i = x - 1, j = y + 1; i >= 0 && j < n; i --, j ++)
            if (grid[i][j] == 'Q')
                return false;

        return true;
    }
};

37. 解数独

判断是 横竖块。可能出现某一种情况是死的，需要剪枝（return false）。

class Solution {
public:
    // 行 列 块(/3 *3)
    void solveSudoku(vector<vector<char>>& board) {
        dfs(board);
    }

    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i ++)
        {
            for (int j = 0; j < 9; j ++)
            {
                if (board[i][j] == '.')
                {
                    for (char k = '1'; k <= '9'; k ++)
                    {
                        if (check(i, j, k, board))
                        {
                            board[i][j] = k;
                            if (dfs(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false; // 9个数都试了 false  剪枝
                }
            }
        }
        return true;
    }

    // 计划在(x, y)填入ch
    bool check(int x, int y, char ch, vector<vector<char>>& board)
    {
        // 横竖
        for (int i = 0; i < 9; i ++)
        {
            if (board[i][y] == ch || board[x][i] == ch) 
                return false;
        }

        // 方块
        int newx = (x / 3) * 3;
        int newy = (y / 3) * 3;
        for (int i = newx; i < newx + 3; i ++)
        {
            for (int j = newy; j < newy + 3; j ++)
            {
                if (board[i][j] == ch)
                    return false;
            }
        }

        return true;
    }
};