网站免费源码大全无需下载公司在线注册

网站免费源码大全无需下载,公司在线注册,wordpress标签页样式,网站制作软件手机思路#xff1a;1.网格问题#xff1a;网格问题是这样的一类搜索问题#xff1a;由mn个小方格组成一个网格#xff0c;每个小方格与其上下左右的四个方格被认为是相邻的#xff0c;要在这样的网格上进行某种搜索。这种题目用DFS实现会非常简单。2.如何构造方格类DFS的代码…思路1.网格问题网格问题是这样的一类搜索问题由m×n个小方格组成一个网格每个小方格与其上下左右的四个方格被认为是相邻的要在这样的网格上进行某种搜索。这种题目用DFS实现会非常简单。2.如何构造方格类DFS的代码1首先每个方格与其上下左右的四个方格相邻则DFS每次要分出四个岔。// 基本的 DFS 框架每次搜索四个相邻方格 void dfs(int[][] grid, int r, int c) { dfs(grid, r - 1, c); // 上边相邻 dfs(grid, r 1, c); // 下边相邻 dfs(grid, r, c - 1); // 左边相邻 dfs(grid, r, c 1); // 右边相邻 }2但是对于网格边缘的方格上下左右并不都有邻居。思路一在递归调用之前判断方格的位置例如位于左边缘则不访问其左邻居。但这样一个一个判断写起来会比较麻烦。×思路二采用“先污染后治理”的思路先做递归调用再在每个DFS函数的开头判断其是否合法不合法的直接返回。同样还需要判断该方格是否有岛屿值是否为1否则也需要返回。√// 处理方格位于网格边缘的情况 void dfs(int[][] grid, int r, int c) { // 若坐标不合法直接返回 if (!(0 r r grid.length 0 c c grid[0].length)) { return; } // 若该方格不是岛屿直接返回 if (grid[r][c] ! 1) { return; } dfs(grid, r - 1, c); dfs(grid, r 1, c); dfs(grid, r, c - 1); dfs(grid, r, c 1); }3但这样还有一个问题那就是DFS可能会不停地兜圈子永远停不下来如下图所示。4那么我们需要标记遍历过的方格保证方格不进行重复遍历。标记遍历过的方格并不需要使用额外空间只需要改变方格中存储的值就可以。在这道题中值为0表示非岛屿不可遍历值为1表示岛屿可遍历可以用2表示已经遍历过的岛屿。5这样就得到了网格DFS遍历的框架代码。// 标记已遍历过的岛屿不做重复遍历 void dfs(int[][] grid, int r, int c) { if (!(0 r r grid.length 0 c c grid[0].length)) { return; } // 已遍历过值为2的岛屿在这里会直接返回不会重复遍历 if (grid[r][c] ! 1) { return; } grid[r][c] 2; // 将方格标记为已遍历 dfs(grid, r - 1, c); dfs(grid, r 1, c); dfs(grid, r, c - 1); dfs(grid, r, c 1); }6如何在DFS遍历时求岛屿的周长求岛屿周长的方法很多如果用DFS遍历来求的话有一种很简单的思路那就是岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量。这里的非岛屿方格既包括水域也包括网格的边界如下图所示。将这个相邻关系对应到DFS遍历中就是每当在DFS遍历中从一个岛屿走向一个非岛屿方格就将周长 1。代码如下所示。int dfs(int[][] grid, int r, int c) { // 从一个岛屿方格走向网格边界周长加 1 if (!(0 r r grid.length 0 c c grid[0].length)) { return 1; } // 从一个岛屿方格走向水域方格周长加 1 if (grid[r][c] 0) { return 1; } if (grid[r][c] ! 1) { return 0; } grid[r][c] 2; return dfs(grid, r - 1, c) dfs(grid, r 1, c) dfs(grid, r, c - 1) dfs(grid, r, c 1); }附代码class Solution { public int islandPerimeter(int[][] grid) { for(int r 0;r grid.length;r){ for(int c 0;c grid[0].length;c){ if(grid[r][c] 1){ //题目限制只有一个岛屿计算一个即可 return dfs(grid,r,c); } } } return 0; } int dfs(int[][] grid,int r,int c){ //先污染后治理只需要在开头判断是否合法若不合法则直接返回 //从一个岛屿方格走向网格边界周长加1 if(!(r 0 r grid.length c 0 c grid[0].length)){ return 1; } //从一个岛屿方格走向水域方格周长加1 if(grid[r][c] 0){ return 1; } //已经遍历过直接返回避免重复遍历 if(grid[r][c] 2){ return 0; } //将本方格标记为已经遍历过 grid[r][c] 2; //探索相邻格子并将四个方向的周长计算结果相加 return dfs(grid,r - 1,c) dfs(grid,r 1,c) dfs(grid,r,c - 1) dfs(grid,r,c 1); } }