回溯法：其他

0051. N 皇后 (opens new window)

题目

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

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

解析

$n$ 个皇后放在 $n \times n$ 棋盘上，因此每行必定有一个皇后，可以依此进行搜索，使用 3 个布尔数组记录列、对角线、反对角线是否存在皇后，在回溯时选择三者不存在的格子放置皇后。

这里用到一个小技巧，可以看到，正反对角线分别有 $2n-1$ 条，因此我们需要将这些对角线分别标号做一下映射，具体方法是，将整个棋盘看作是一个坐标系，我们可以使用直线的截距作为标号。其中，正对角线计算方法如下：

$y=-x+b \Rightarrow b=y+x$

反对角线计算方法如下：

$y=x+b \Rightarrow b=y-x$

需要注意的是，$y-x$ 可能小于 0，这里可以增加一个偏移量，即 $b=y-x+n$。

代码

class Solution {
    vector<bool> col, dg, udg;
    vector<string> path;
    vector<vector<string>> ans;
public:
    vector<vector<string>> solveNQueens(int n) {
        col = vector<bool>(n);
        dg = udg = vector<bool>(2 * n);
        path = vector<string>(n, string(n, '.'));

        dfs(0, n);
        return ans;
    }

    void dfs(int x, int n) {
        if (x == n) {
            ans.push_back(path);
            return;
        }
        for (int y = 0; y < n; y++) {
            if (col[y] || udg[y - x + n] || dg[y + x]) continue;
            col[y] = udg[y - x + n] = dg[y + x] = true;
            path[x][y] = 'Q';
            dfs(x + 1, n);
            path[x][y] = '.';
            col[y] = udg[y - x + n] = dg[y + x] = false;
        }
    }
};

0052. N皇后 II (opens new window)

题目

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

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

解析

本题与 0051. N 皇后 解法完全一致，只需把统计组合方案改为统计数量即可。

代码

class Solution {
    vector<bool> col, dg, udg;
    int ans = 0;
public:
    int totalNQueens(int n) {
        col = vector<bool>(n);
        dg = udg = vector<bool>(2 * n);

        dfs(0, n);
        return ans;
    }

    void dfs(int x, int n) {
        if (x == n) {
            ans++;
            return;
        }
        for (int y = 0; y < n; y++) {
            if (col[y] || udg[y - x + n] || dg[y + x]) continue;
            col[y] = udg[y - x + n] = dg[y + x] = true;
            dfs(x + 1, n);
            col[y] = udg[y - x + n] = dg[y + x] = false;
        }
    }
};

0079. 单词搜索 (opens new window)

题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

解析

枚举矩阵的每个位置作为单词的起点，只要能找到对应单词就直接返回 true。

具体在每次搜索中，可以依次尝试相邻未访问格子的字母，只要能和单词对应位置匹配，就继续向下搜索。

代码

class Solution {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (dfs(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string& word, int idx, int x, int y) {
        if (board[x][y] != word[idx]) return false;
        if (idx == word.length() - 1) return true;

        char t = board[x][y];
        board[x][y] = '.';
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= board.size() || ny < 0 || ny >= board[0].size() || board[nx][ny] == '.') continue;
            if (dfs(board, word, idx + 1, nx, ny)) return true;
        }
        board[x][y] = t;
        return false;
    }
};

0093. 复原 IP 地址 (opens new window)

题目

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

解析

将 IP 地址拆分成四个数字，枚举每个数字能截取的字符串的位置，当四个数字都确定，并且枚举到了字符串的最后一位，说明是一个合法方案，将其加入结果。

代码

class Solution {
    vector<string> ans;
    vector<int> cur;
public:
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0);
        return ans;
    }

    void dfs(string& s, int idx, int start) {
        if (idx == 4 && start == s.length()) {
            string ip = to_string(cur[0]);
            for (int i = 1; i < cur.size(); i++) {
                ip += "." + to_string(cur[i]);
            }
            ans.push_back(ip);
            return;
        }
        for (int i = start, num = 0; i < s.length(); i++) {
            num = num * 10 + s[i] - '0';
            if (num > 255) break;
            cur.push_back(num);
            dfs(s, idx + 1, i + 1);
            cur.pop_back();
            if (num == 0) break;
        }
    }
};

0291. 单词规律 II (opens new window)

题目

解析

代码

0351. 安卓系统手势解锁 (opens new window)

题目

解析

代码

0488. 祖玛游戏 (opens new window)

题目

解析

代码