✨今日算法一题
文章目录
二维网格中探测环
题目描述
思路详解
使用dfs来检测是否有环
有环的条件就是在搜索的过程中搜索到 该次 dfs已经访问过的坐标
定义一个二维数组记录以及访问过的坐标
考虑根据在搜索的过程中添加上一层搜索过来的方向，不搜索该方向的反方向
在这种情况下如果找到已经访问过的节点就说明有环，有环就直接返回
代码与结果
class Solution { boolean[][] visited; char[][] grid; int m, n; boolean hasRing; public boolean containsCycle(char[][] grid) { this.grid = grid; m = grid.length; n = grid[0].length; visited = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j]){ dfs(i, j, grid[i][j], 'L'); if (hasRing) return true; } } } return false; } private void dfs(int i, int j, char ch, char from) { if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != ch){ return; } if (visited[i][j]) { hasRing = true; return; } visited[i][j] = true; if (from != 'L') dfs(i, j - 1, ch, 'R'); if (from != 'R') dfs(i, j + 1, ch, 'L'); if (from != 'U') dfs(i - 1, j, ch, 'D'); if (from != 'D') dfs(i + 1, j, ch, 'U'); } }
✨总结
本节练习了dfs破环，值得多练几次哦！！！
