【Leetcode】dfs深度優先搜尋

經典題目

• • 46. 全排列
  • 47. 全排列II
  • 37. 解數獨
  • 51. N皇後

46. 全排列

leetcode 46

class Solution {
public:
    vector<vector<int>> ans;

    // 判斷目前數字是否被使用過（基于原始數列沒有重複元素）
    bool isValid(vector<int>& res, int num) {
        for(int& n : res) {
            if(n == num) return false;
        }
        return true;
    }

    void dfs(vector<int>& nums, vector<int>& res){
        // 找到一組排列，加入ans，傳回
        if(res.size() == nums.size()){
            ans.push_back(res);
            return;
        }
        // 周遊目前位置所有可能取值
        for(int i = 0; i < nums.size(); i++){
            if(!isValid(res, nums[i])) continue;
            res.push_back(nums[i]);
            dfs(nums, res);
            res.pop_back();  // 回退
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        // 聲明一個存儲可能排列的容器
        vector<int> res;
        // 因為所有可能性都要被找出，是以dfs為void型函數，需要疊代各種可能性
        dfs(nums, res);
        return ans;
    }
};
           

47. 全排列II

leetcode 47

class Solution {
public:
    vector<vector<int>> ans;

    void dfs(vector<int>& nums, vector<int>& res, vector<int>& visited) {
        // 找到一組排列，加入ans，傳回
        if(res.size() == nums.size()) {
            ans.push_back(res);
            return;
        }
        // 周遊目前位置所有可能取值
        for(int i = 0; i < nums.size(); i++) {
            if(visited[i]) continue;
            res.push_back(nums[i]);
            visited[i] = 1;
            dfs(nums, res, visited);
            res.pop_back(); // 回退
            visited[i] = 0; // 回退
            while(i + 1 < nums.size() && nums[i] == nums[i+1]) i++; // 不斷跳過重複的元素
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 先排序！使得重複的元素緊挨在一起
        vector<int> res;
        vector<int> visited(nums.size()); // 記錄通路過的元素
        // 因為所有可能性都要被找出，是以dfs為void型函數，需要疊代各種可能性
        dfs(nums, res, visited);
        return ans;
    }
};
           

37. 解數獨

leetcode 37

class Solution {
public:
    // 判斷目前位置（i,j）能否放置值ch
    bool isValid(const vector<vector<char>>& board, char ch, int i, int j) {
        for(int k = 0; k < 9; k++) {
            if(board[k][j] == ch) return false; // 列
            if(board[i][k] == ch) return false; // 行
            if(board[(i/3)*3 + k/3][(j/3)*3 + k%3] == ch) return false; // 3x3方格
        }
        return true;
    }

    bool dfs(vector<vector<char>>& board, int i, int j) {
        int n = 9;
        // 搜尋完目前行跳到下一行第一位
        if(j == 9) {
            return dfs(board, i + 1, 0);
        }
        // 搜尋完所有行，結束，傳回true
        if(i == 9) {
            return true;
        }
        // 如果目前位置已經有數字，則跳過
        if(board[i][j] != '.') {
            return dfs(board, i, j + 1);
        }
        // 對目前位置（i,j）周遊1~9
        for(char ch = '1'; ch <= '9'; ch++) {
            if(!isValid(board, ch, i, j)) continue;
            board[i][j] = ch;
            if(dfs(board, i, j + 1)) return true; // 找到直接退出
            board[i][j] = '.';
        }
        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        // 因為隻有一個解，是以dfs為bool類型函數，找到直接退出，無需周遊其他可能
        dfs(board, 0, 0); 
        return;
    }
};
           

51. N皇後

leetcode 51

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

    // 判斷目前位置能否放置皇後
    bool isValid(vector<string>& map, int i, int j, int n) {
        for(int k = 0; k < n; k++) {
            // 判斷水準和豎直方向
            if(map[i][k] == 'Q') return false;
            if(map[k][j] == 'Q') return false;
            // 判斷對角線的四個方向
            if(k <= i && k <= j && map[i-k][j-k] == 'Q') return false;
            if(k + i < n && k + j < n && map[i+k][j+k] == 'Q') return false;
            if(k <= i && k + j < n && map[i-k][j+k] == 'Q') return false;
            if(k + i < n && k <= j && map[i+k][j-k] == 'Q') return false;
        }
        return true;
    }

    void dfs(vector<string>& map, int i, int n) {
        // 最後一行搜尋完成後傳回
        if(i == n) {
            ans.push_back(map);
            return;
        }
        // 對目前行i的每一個位置搜尋
        for(int j = 0; j < n; j++) {
            if(!isValid(map, i, j, n)) continue;
            map[i][j] = 'Q';
            dfs(map, i+1, n);
            map[i][j] = '.'; // 回退
        }
        return;
    }

    vector<vector<string>> solveNQueens(int n) {
        // 初始化一個棋盤格
        vector<string> map(n);
        string init(n, '.');
        for(int i = 0; i < n; i++) map[i] = init; 
        // 因為所有可能性都要被找出，是以dfs為void型函數，需要疊代各種可能性
        dfs(map, 0, n);
        return ans;
    }
};