当前位置: 首页 > news >正文

32.递归、搜索、回溯之floodfill算法

0.简介

1.图像渲染

. - 力扣(LeetCode)

题目解析

算法原理

代码

class Solution {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };int m, n;int prev;public int[][] floodFill(int[][] image, int sr, int sc, int color) {if (image[sr][sc] == color)return image;m = image.length;n = image[0].length;prev = image[sr][sc];dfs(image, sr, sc, color);return image;}public void dfs(int[][] image, int i, int j, int color) {image[i][j] = color;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {dfs(image, x, y, color);}}}
}

2.岛屿数量

. - 力扣(LeetCode)

题目解析

算法原理

代码

class Solution {boolean[][] vis;int m, n;int[] dx = { 0, 0, -1, 1 };int[] dy = { 1, -1, 0, 0 };public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m][n];int ret = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (!vis[i][j] && grid[i][j] == '1') {ret++;dfs(grid, i, j);}}return ret;}public void dfs(char[][] grid, int i, int j) {vis[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1') {dfs(grid, x, y);}}}
}

3.岛屿的最大面积

. - 力扣(LeetCode)

题目解析

算法原理

代码

class Solution {boolean[][] vis;int m, n;int[] dx = { 0, 0, -1, 1 };int[] dy = { 1, -1, 0, 0 };int count;public int maxAreaOfIsland(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m][n];int ret = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (!vis[i][j] && grid[i][j] == 1) {count = 0;dfs(grid, i, j);ret = Math.max(ret, count);}}return ret;}public void dfs(int[][] grid, int i, int j) {count++;vis[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)dfs(grid, x, y);}}
}

4.被围绕的区域

130. 被围绕的区域 - 力扣(LeetCode)

题目解析

算法原理

代码

class Solution {int m, n;int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };public void solve(char[][] board) {m = board.length;n = board[0].length;// 1. 先把边界的 O 相连的联通块,全部修改成 '.'for (int j = 0; j < n; j++) {if (board[0][j] == 'O')dfs(board, 0, j);if (board[m - 1][j] == 'O')dfs(board, m - 1, j);}for (int i = 0; i < m; i++) {if (board[i][0] == 'O')dfs(board, i, 0);if (board[i][n - 1] == 'O')dfs(board, i, n - 1);}// 2. 还原for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (board[i][j] == '.')board[i][j] = 'O';else if (board[i][j] == 'O')board[i][j] = 'X';}}public void dfs(char[][] board, int i, int j) {board[i][j] = '.';for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {dfs(board, x, y);}}}
}

5.太平洋大西洋水流问题

. - 力扣(LeetCode)

题目解析

算法原理

代码

class Solution {int m, n;int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };public List<List<Integer>> pacificAtlantic(int[][] h) {m = h.length;n = h[0].length;boolean[][] pac = new boolean[m][n];boolean[][] atl = new boolean[m][n];// 1. 先处理 pac 洋for (int j = 0; j < n; j++)dfs(h, 0, j, pac);for (int i = 0; i < m; i++)dfs(h, i, 0, pac);// 2. 再处理 atl 洋for (int i = 0; i < m; i++)dfs(h, i, n - 1, atl);for (int j = 0; j < n; j++)dfs(h, m - 1, j, atl);// 3. 提取结果List<List<Integer>> ret = new ArrayList<>();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (pac[i][j] && atl[i][j]) {List<Integer> tmp = new ArrayList<>();tmp.add(i);tmp.add(j);ret.add(tmp);}return ret;}public void dfs(int[][] h, int i, int j, boolean[][] vis) {vis[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >= h[i][j]) {dfs(h, x, y, vis);}}}
}

6.扫雷问题

. - 力扣(LeetCode)

题目解析

算法原理

代码

class Solution {int[] dx = { 0, 0, 1, -1, 1, 1, -1, -1 };int[] dy = { 1, -1, 0, 0, 1, -1, 1, -1 };int m, n;public char[][] updateBoard(char[][] board, int[] click) {m = board.length;n = board[0].length;int x = click[0], y = click[1];if (board[x][y] == 'M') // 如果直接点到地雷,游戏结束{board[x][y] = 'X';return board;}dfs(board, x, y);return board;}public void dfs(char[][] board, int i, int j) {// 统计⼀下周围地雷的个数int count = 0;for (int k = 0; k < 8; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {count++;}}if (count == 0) // 周围没有地雷{board[i][j] = 'B';for (int k = 0; k < 8; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {dfs(board, x, y);}}} else {board[i][j] = (char) ('0' + count);return;}}
}

7.机器人的运动范围

. - 力扣(LeetCode)

题目解析

算法原理

代码

class Solution {int m, n, k;boolean[][] vis;int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };int ret;public int movingCount(int _m, int _n, int _k) {m = _m;n = _n;k = _k;vis = new boolean[m][n];dfs(0, 0);return ret;}public void dfs(int i, int j) {ret++;vis[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y)) {dfs(x, y);}}}public boolean check(int i, int j) {int tmp = 0;while (i != 0) {tmp += i % 10;i /= 10;}while (j != 0) {tmp += j % 10;j /= 10;}return tmp <= k;}
}

http://www.lryc.cn/news/439879.html

相关文章:

  • Vue3.5+ 响应式 Props 解构
  • k8s中的认证授权
  • Leetcode 3291. Minimum Number of Valid Strings to Form Target I
  • PostgreSQL的查看主从同步状态
  • Java多态性的理解
  • 安全工具 | 使用Burp Suite的10个小tips
  • 企业项目中字符串工具类
  • 下载github patch到本地
  • C++基础部分代码
  • neo4j(spring) 使用示例
  • 链接升级:Element UI <el-link> 的应用
  • 简单题26 - 删除有序数组中的重复项(Java)20240917
  • DFS:深搜+回溯+剪枝实战解决OJ问题
  • 命令语境中的“可以”的字词含义分析
  • 直播相关03-录制麦克风声音, ffmpeg 命名,使用命令行完成录音
  • VUE3中ref与reactive
  • 高职院校人工智能技术和无人机技术实训室建设方案
  • x-cmd pkg | shtris: 在终端体验经典的俄罗斯方块游戏
  • Linux基础---07文件传输及解决yum安装失效的方法
  • [项目][WebServer][Makefile Shell]详细讲解
  • ElementUI大坑Notification修改样式
  • vivado中的diagram
  • 项目实现:云备份②(文件操作、Json等工具类的实现)
  • ‌内网穿透技术‌总结
  • Git使用—把当前仓库的一个分支push到另一个仓库的指定分支、基于当前仓库创建另一个仓库的分支并推送到对应仓库(mit6828)
  • windows11+ubuntu20.04.6双系统安装
  • 如何通过 PhantomJS 模拟用户行为抓取动态网页内容
  • ARM驱动学习之8 动态申请字符类设备号
  • TCP.IP四层模型
  • 极狐GitLab DevSecOps 功能合集(七大安全功能)