Leetcode1020飞地的数量-----深度优先搜索
2022/4/19 23:18:47
本文主要是介绍Leetcode1020飞地的数量-----深度优先搜索,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目表述
给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例:
深度优先搜索
该题思路和岛屿数量比较相似,根据飞地的定义,如果从一个陆地单元格出发无法移动到网格边界,则这个陆地单元格是飞地。因此可以将所有陆地单元格分成两类:第一类陆地单元格和网格边界相连,这些陆地单元格不是飞地;第二类陆地单元格不和网格边界相连,这些陆地单元格是飞地。
我们可以从网格边界上的每个陆地单元格开始深度优先搜索,遍历完边界之后,所有和网格边界相连的陆地单元格就都被访问过了。然后遍历整个网格,如果网格中的一个陆地单元格没有被访问过,则该陆地单元格不和网格的边界相连,是飞地。
在实现时,不用将整个二维数组全部遍历,只用遍历网格的边界即可,找边界值为1的坐标,dfs搜索与该边界连通的值即可。
class Solution { private int[][] directions = {{1,0},{-1,0},{0,-1},{0,1}}; public int numEnclaves(int[][] grid) { int count = 0; int m = grid.length; int n = grid[0].length; boolean[][] visited = new boolean[grid.length][grid[0].length]; for(int i = 0;i < m; i++){ dfs(i,0,visited,grid); dfs(i,n-1,visited,grid); } for(int i = 1; i < n-1;i++){ dfs(0,i,visited,grid); dfs(m-1,i,visited,grid); } for(int i = 0; i < m;i++){ for(int j = 0; j < n; j++){ if(grid[i][j] == 1 && !visited[i][j]){ count++; } } } return count; } public void dfs(int row, int col, boolean[][] visited, int[][] grid){ if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length){ return; } if(visited[row][col] == true){ return; } if(grid[row][col] == 0){ return ; } visited[row][col] = true; for(int[] dir:directions){ dfs(row+dir[0], col + dir[1], visited, grid); } } }
这篇关于Leetcode1020飞地的数量-----深度优先搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升