算法|图论 5

LeetCode 841- 钥匙和房间

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述：有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

解题思路（广度优先遍历）：

这题需要注意，本题是一道有向图的题，前面的题基本上都是无向图。首先，将第一个房间的钥匙进队，然后当队列不为空时，不断出队。打开对应的门，拿钥匙，如果之前这个门已经开过了。就直接continue。否则就将这个钥匙能开的门入队。

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(),false);//来记录我们能打开的门
        queue<vector<int>> que;//存储能打开的门的钥匙组
        que.push(rooms[0]);
        while(!que.empty()){
            vector<int> tmp = que.front();
            que.pop();
            for(int i=0;i<tmp.size();i++){
                if(visited[tmp[i]] == false){//若这门被开过了，直接跳过，不然可能会死循环
                    que.push(rooms[tmp[i]]);
                    visited[tmp[i]] = true;
                }
            }
        }
        for(int i=1;i<rooms.size();i++){
            if(visited[i] == false) return false;
        }
        return true;
    }
};

总结：

• 一道简单的有向图，主要是不要重复去开同一个门。思路还是比较简单的。

LeetCode 463- 岛屿的周长

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述：给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

解题思路

思路一：

遍历所有的格子，首先判断不是陆地就continue，是陆地我们就对其四个方向进行侦测，若是海洋或边界则说明这个方向对应的有一个边可以当作周长加上。即res++。

class Solution {
public:
    int direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    int islandPerimeter(vector<vector<int>>& grid) {
        int result = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {       // 上下左右四个方向
                        int x = i + direction[k][0];
                        int y = j + direction[k][1];    // 计算周边坐标x,y
                        if (x < 0                       // i在边界上
                                || x >= grid.size()     // i在边界上
                                || y < 0                // j在边界上
                                || y >= grid[0].size()  // j在边界上
                                || grid[x][y] == 0) {   // x,y位置是水域
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
};

思路二：

通过观察可以看出来，只要有一对岛屿挨在一起，那么其总周长就应该减2。故我们只需要判断当前点是否有挨着岛屿即可，有则面积-2。注意，我们只需要讨论 左边和上边 或 右边和下边 即可。因为会遍历所有的岛屿，防止重复遍历了。

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int sum = 0;    // 陆地数量
        int cover = 0;  // 相邻数量
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    sum++;
                    // 统计上边相邻陆地
                    if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
                    // 统计左边相邻陆地
                    if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
                    // 为什么没统计下边和右边？ 因为避免重复计算
                }
            }
        }
        return sum * 4 - cover * 2;
    }
}

总结：

• 开始自己想的是广度优先，每次遍历的时候再判断每个点的四周，没想到这么简单的思路就可以了。因为我们不需要求多个岛屿。只有一个岛屿，所以可以这样。若是求多个岛屿的周长，那可能就需要广度优先加判断了。