Leetcode797.所有可能的路径
文章链接：代码随想录
题目链接：797.所有可能的路径
思路：深搜入门，注意邻接表和邻接矩阵的形式
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void dfs(vector<vector<int>>& graph, int x){
if (x == graph.size() - 1){
result.push_back(path);
return ;
}
for (int i = 0; i < graph[x].size(); i++){
path.push_back(graph[x][i]);
dfs(graph, graph[x][i]);
path.pop_back();
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
path.push_back(0);
dfs(graph, 0);
return result;
}
};
Leetcode200. 岛屿数量
思路：深搜法
class Solution {
public:
int dir[4][2] = {
1, 0, -1, 0, 0, 1, 0, -1};
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){
for (int i = 0; i < 4; i++){
int nex = x + dir[i][0];
int ney = y + dir[i][1];
if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue ;
if (!visited[nex][ney] && grid[nex][ney] == '1'){
visited[nex][ney] = true;
dfs(grid, visited, nex, ney);
}
}
}
int numIslands(vector<vector<char>>& grid) {
int result = 0;
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), 0));
for (int i = 0; i < grid.size(); i++){
for (int j = 0; j < grid[0].size(); j++){
if (!visited[i][j] && grid[i][j] == '1'){
result++;
visited[i][j] = true;
dfs(grid, visited, i, j);
}
}
}
return result;
}
};
广搜法，用队列存储，遍序搜寻，替代深搜回溯
class Solution {
public:
int dir[4][2] = {
1, 0, -1, 0, 0, 1, 0, -1};
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){
queue<pair<int, int>> que;
que.push({
x, y});
visited[x][y] = true;
while(!que.empty()){
pair<int, int> cur = que.front();
que.pop();
for (int i = 0; i < 4; i++){
int nex = cur.first + dir[i][0];
int ney = cur.second + dir[i][1];
if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue ;
if (!visited[nex][ney] && grid[nex][ney] == '1'){
que.push({
nex, ney});
visited[nex][ney] = true;
}
}
}
}
int numIslands(vector<vector<char>>& grid) {
int result = 0;
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), 0));
for (int i = 0; i < grid.size(); i++){
for (int j = 0; j < grid[0].size(); j++){
if (!visited[i][j] && grid[i][j] == '1'){
result++;
bfs(grid, visited, i, j);
}
}
}
return result;
}
};
图论第一天打卡，加油！！！
