第二十七天
我使用的C++，错误的地方请见谅，文章初衷仅用来督促本人学习，如果恰巧能够给你带来帮助，我会十分开心。
文章目录
一、130. 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int m, n;
void dfs(vector<vector<char>>& board, int x, int y){
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O'){
return;
}
board[x][y] = 'A';//将与边界相连的O标记为A，并向四周扩散
dfs(board, x, y + 1);
dfs(board, x, y - 1);
dfs(board, x + 1, y);
dfs(board, x - 1, y);
}
void solve(vector<vector<char>>& board) {
//能活的棋子必然与边界相连，所以从边界上的o开始遍历，将棋盘中间接或直接相连的o标记为A，随后只需将A改为O，没有标记为A的o改为X即可
//深度遍历尝试
m = board.size();
if (m == 0){
return;
}
n = board[0].size();
for (int i = 0; i < m; ++i){//左右两个边界
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int i = 0; i < n; ++i){
dfs(board, 0, i);
dfs(board, m - 1, i);
}
for (int i = 0; i < m; ++i){
for (int j = 0; j < n; ++j){
if (board[i][j] == 'A'){
board[i][j] = 'O';
}
else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
};
二、797. 所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-paths-from-source-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
vector<vector<int>> ans;
vector<int> stack;//利用栈来储存路径
void dfs(vector<vector<int>>& graph, int x, int n){
if (x == n){
ans.push_back(stack);
}
for (auto& y : graph[x]){//将每一个点可以到访的点进行遍历
stack.push_back(y);
dfs(graph, y, n);
stack.pop_back();
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
//有向无环图，意味着一条路径中一个点只会遍历到一次，不会出现重复遍历的情况，不需要另作标记
//深度遍历每一条路径
stack.push_back(0);
dfs(graph, 0, graph.size() - 1);//从0开始遍历
return ans;
}
};
三、78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution {
public:
vector<vector<int>> ans;
vector<int> stk;
void dfs (vector<int>& nums, int cur){
if (cur == nums.size()){
ans.push_back(stk);
return;
}
stk.push_back(nums[cur]);//一个选取，一个不选取，可以完美实现全排列
dfs(nums, cur + 1);
stk.pop_back();
dfs(nums, cur + 1);
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ans;
}
};