国外做节目包装的网站,域名连接到网站吗,黄冈网站推广收费标准,wordpress 稳定版在单位摸鱼#xff0c;地铁上看了个开始#xff0c;图论开了个头#xff0c;后面也希望能往这个方向上转#xff0c;努努力吧。
一周没做题啦#xff0c;后面坚持继续做题#xff0b;二刷#xff0c;接着记录每一天#xff01;#xff01;#xff01;加油#xff0…在单位摸鱼地铁上看了个开始图论开了个头后面也希望能往这个方向上转努努力吧。
一周没做题啦后面坚持继续做题二刷接着记录每一天加油
DFS和BFS起步
797.所有可能的路径
DFS最基本应用
class Solution {
public:vectorvectorintresult;vectorintpath;vectorvectorint allPathsSourceTarget(vectorvectorint graph) {path.push_back(0);findpath(graph,0);return result;}void findpath(vectorvectorint graph,int cur){if(cur graph.size() - 1){result.push_back(path);return;}for(int i 0;i graph[cur].size();i){path.push_back(graph[cur][i]);findpath(graph,graph[cur][i]);path.pop_back();}}
};
200.岛屿数量
DFS思路主要还是要和回溯放一块搞
class Solution {
public:int result 0;int neighbor[4][2] {1,0,-1,0,0,1,0,-1};int numIslands(vectorvectorchar grid) {int x grid.size();int y grid[0].size();vectorvectorboolvisited(x,vectorbool(y,false));for(int n 0;n x; n){for(int m 0; m y;m){if(grid[n][m] 1 visited[n][m] 0){visited[n][m] 1;result;dfs(grid,visited,n,m);}}}return result;}void dfs(vectorvectorchar grid,vectorvectorbool visited,int x,int y){for(int i 0;i 4;i){int nextx x neighbor[i][0];int nexty y neighbor[i][1];if(nextx 0 || nexty 0 || nextx grid.size() || nexty grid[0].size())continue;if(visited[nextx][nexty] 0 grid[nextx][nexty] 1){visited[nextx][nexty] 1;dfs(grid,visited,nextx,nexty);}}}
};
BFS主要是while循环
class Solution {
public:int result 0;int neighbor[4][2] {1,0,0,1,-1,0,0,-1};int numIslands(vectorvectorchar grid) {int n grid.size();int m grid[0].size();vectorvectorboolvisited(n,vectorbool(m,false));for(int i 0;i n;i){for(int j 0;j m;j){if(visited[i][j] 0 grid[i][j] 1){result;bfs(grid,visited,i,j);}}}return result;}void bfs(vectorvectorchar grid, vectorvectorbool visited,int x,int y){queuepairint,intque;que.push({x,y});visited[x][y] 1;while(!que.empty()){pairint,intcur que.front();que.pop();for(int i 0;i 4;i){int nextx cur.first neighbor[i][0];int nexty cur.second neighbor[i][1];if(nextx 0 || nexty 0 || nextx grid.size() || nexty grid[0].size())continue;if(visited[nextx][nexty] 0 grid[nextx][nexty] 1){que.push({nextx,nexty});visited[nextx][nexty] 1;}}}}
};
今天就这两道题明天接着来~摸鱼
