代碼隨想錄圖論 第五天| 841.鑰匙和房間
一、 841.鑰匙和房間
題目鏈接：https://leetcode.cn/problems/keys-and-rooms/
思路：鑰匙就是索引，遍歷過(guò)就標(biāo)記，每拿到一個(gè)房間的鑰匙，直接for循環(huán)遞歸遍歷，深度優(yōu)先直接拿下。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-738320.html
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] visited = new boolean[rooms.size()];
dfs(visited, rooms, 0);
for (boolean b : visited) {
if (b == false) return false;
}
return true;
}
void dfs(boolean[] visited, List<List<Integer>> rooms, int key) {
if (visited[key]) return;
visited[key] = true;
List<Integer> list = rooms.get(key);
for (Integer i : list) {
dfs(visited, rooms, i);
}
}
}
二、463. 島嶼的周長(zhǎng)
題目鏈接：https://leetcode.cn/problems/island-perimeter/
思路：常規(guī)思路，遍歷每一個(gè)島嶼并且計(jì)算當(dāng)前點(diǎn)的邊長(zhǎng)就可以。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-738320.html
class Solution {
int sum = 0;
public int islandPerimeter(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
dfs(grid, i, j);
return sum;
}
}
}
return sum;
}
void dfs(int[][] grid, int x, int y) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
return;
}
if (grid[x][y] == 2 || grid[x][y] == 0) return;
grid[x][y] = 2;
if (x-1 < 0 || grid[x-1][y] == 0) sum++;
if (x+1 >= grid.length || grid[x+1][y] == 0) sum++;
if (y-1 < 0 || grid[x][y-1] == 0) sum++;
if (y+1 >= grid[0].length || grid[x][y+1] == 0) sum++;
dfs(grid, x-1, y);
dfs(grid, x+1, y);
dfs(grid, x, y-1);
dfs(grid, x, y+1);
}
}
到了這里，關(guān)于代碼隨想錄圖論 第五天| 841.鑰匙和房間 463. 島嶼的周長(zhǎng)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
