如何建立个人免费网站,建设工程合同范本2021,html书店网站建设,石化建设分会网站# 图论第3天----第841题、第463题 文章目录 一、第841题--钥匙和房间二、第463题--岛屿的周长 又继续开始修行#xff0c;把图论这块补上#xff0c;估计要个5-6天时间。
一、第841题–钥匙和房间
有向图的遍历。dfs遍历3部曲做#xff0c;思路也较顺----访问过的把图论这块补上估计要个5-6天时间。
一、第841题–钥匙和房间
有向图的遍历。dfs遍历3部曲做思路也较顺----访问过的就直接返回没访问过的就设为true。注意这里不需要回溯因为不是找出一条路径来覆盖到所有的节点而是能覆盖到就行不要求一条路径来覆盖。
class Solution {
public:void dfs(vectorvectorint rooms, vectorbool visited, int x){if(visited[x]) return;visited[x] true;for(int t : rooms[x]){dfs(rooms, visited, t);}}bool canVisitAllRooms(vectorvectorint rooms) {vectorbool visited(rooms.size(), false);dfs(rooms, visited, 0);for(int i0; irooms.size(); i){if(visited[i] false) return false;}return true;}
};二、第463题–岛屿的周长
这个题跟dfs三部曲没关系属于找规律。根据土地的数量、相邻地块的数量获得最终的结果----num4 - count2;
class Solution {
public:int islandPerimeter(vectorvectorint grid) {int n grid.size();int m grid[0].size();int num0;int count0;for(int i0; in; i){for(int j0; jm; j){if(grid[i][j] 1){num;if(i0 grid[i-1][j] 1) count;if(j0 grid[i][j-1] 1) count;} }}return num*4 - count*2;}
};
