图论第3天----第841题、第463题

# 图论第3天----第841题、第463题

文章目录

一、第841题--钥匙和房间
二、第463题--岛屿的周长

又继续开始修行，把图论这块补上，估计要个5-6天时间。

一、第841题–钥匙和房间

有向图的遍历。dfs遍历3部曲做，思路也较顺----访问过的，就直接返回；没访问过的，就设为true。注意，这里不需要回溯，因为不是找出一条路径来覆盖到所有的节点，而是能覆盖到就行，不要求一条路径来覆盖。

class Solution {
public:
    void dfs(vector>& rooms, vector& visited, int x){
        if(visited[x]) return;
        visited[x] = true;
        for(int t : rooms[x]){
            dfs(rooms, visited, t);
        }
    }

    bool canVisitAllRooms(vector>& rooms) {
        vector visited(rooms.size(), false);
        dfs(rooms, visited, 0);
        for(int i=0; i

二、第463题–岛屿的周长

这个题跟dfs三部曲没关系，属于找规律。根据土地的数量、相邻地块的数量，获得最终的结果----num4 - count2;

class Solution {
public:
    int islandPerimeter(vector>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int num=0;
        int count=0;
        for(int i=0; i0 && grid[i-1][j] == 1) count++;
                    if(j>0 && grid[i][j-1] == 1) count++;
                } 
            }
        }
        return num*4 - count*2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

相关阅读:
虚拟机扩容
【深入浅出C#】章节 9: C#高级主题：反射和动态编程
汽车研发项目进度管理的挑战与优化策略
基于STM32单片机的温度报警器（数码管)（Proteus仿真+程序）
11. Vue3组件的更新渲染逻辑
Java学习笔记（十四）：String类
编程中老生常谈的【编码规范】你还记得多少？进来回顾一下吧【文末送书】
topic是什么
Worthington磷脂酶A2研究丨磷脂酰胆碱2-乙酰水解酶
香豆素修饰牛血清白蛋白,coumarin-Bovine Serum Albumin,BSA-coumarin

原文地址：https://blog.csdn.net/u013441272/article/details/133668211