來自靈神網格圖題單。

1. 網格圖

1.1. LC 200 島嶼數量

這題我一開始想繁了，想維護并查集，然后看等價類個數。其實完全沒有必要。因為連通分量深搜到頭就可以直接給答案計數+1。利用vis數組維護訪問過的點，然后碰到新連通分量重新深搜即可。因為有vis數組，所以每個節點至多訪問一次，即O(nm)的復雜度。

import java.util.Arrays;class Solution {boolean[] vis;int m,n;int[][] direction = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m*n];int ans = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(grid[i][j]=='1'&&!vis[i*n+j]){dfs(grid,i,j);ans++;}}}return ans;}private void dfs(char[][] grid,int x,int y){if(vis[x*n+y]){return;}vis[x*n+y] = true;int nx,ny;for (int[] dir : direction) {nx = x+dir[0];ny = y+dir[1];if(indexValid(nx,ny)&&grid[nx][ny]=='1'){dfs(grid,nx,ny);}}}private boolean indexValid(int x,int y){return x>=0 && x<m && y>=0 && y<n;}
}

1.2. LC 695 島嶼的最大面積

這題和LC 200其實一樣的。前者統計連通分量個數，這個統計最大連通分量元素個數。還是維護vis防止走重復，遇到新連通分支就統計這個連通分支元素數量，維護最大值就行。

class Solution {boolean[] vis;int m,n;int[][] directions = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};public int maxAreaOfIsland(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[n*m];int max = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(!vis[i*n+j] && grid[i][j]==1){max = Math.max(max,dfs(grid,i,j));}}}return max;}private int dfs(int[][] g,int x,int y){if(vis[x*n+y]){return 0;}vis[x*n+y] = true;int nx,ny;int cnt = 0;for (int[] direction : directions) {nx = x+direction[0];ny = y+direction[1];if(indexValid(nx,ny) && g[nx][ny]==1){cnt += dfs(g,nx,ny);}}return cnt+1;}private boolean indexValid(int x,int y){return x>=0 && x<m && y>=0 && y<n;}
}

1.3. LC 面試題16.19. 水域大小

和LC695差不多。維護每個連通分量大小，排個序返回就行。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {boolean[] vis;int m,n;int[][] dirs = new int[][]{{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};public int[] pondSizes(int[][] land) {m = land.length;n = land[0].length;vis = new boolean[m*n];List<Integer> tmp = new ArrayList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(!vis[i*n+j]&&land[i][j]==0){tmp.add(dfs(land,i,j));}}}int[] ans = new int[tmp.size()];for (int i = 0; i < tmp.size(); i++) {ans[i] = tmp.get(i);}Arrays.sort(ans);return ans;}private int dfs(int[][] l,int x,int y){if(vis[x*n+y]){return 0;}vis[x*n+y]=true;int cnt = 0;int nx,ny;for (int[] dir : dirs) {nx = x+dir[0];ny = y+dir[1];if(indexValid(nx,ny)&&l[nx][ny]==0){cnt += dfs(l,nx,ny);}}return cnt+1;}private boolean indexValid(int x,int y){return x>=0 && x<m && y>=0 && y<n;}
}

1.4. LC 463 島嶼的周長

和200/695/16.19差不多，就是查一個連通分量。記得重復邊不僅沒有增量反而-1。另外由于題目明確說了就一個連通分量，因此查到一個后可以直接結束了。

class Solution {boolean[] vis;int m,n;int[][] dirs = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};public int islandPerimeter(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m*n];int ans = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(!vis[i*n+j]&&grid[i][j]==1){ans = dfs(grid,i,j);break;}}}return ans;}private int dfs(int[][] g,int x,int y){if(vis[x*n+y]){return 0;}vis[x*n+y]=true;int cnt = 4;int nx,ny;for (int[] dir : dirs) {nx = x+dir[0];ny = y+dir[1];if(indexValid(nx,ny)&&g[nx][ny]==1){cnt+=dfs(g,nx,ny)-1;}}return cnt;}private boolean indexValid(int x,int y){return x>=0 && x<m && y>=0 && y<n;}
}

1.5. LC 2658 網格圖中魚的最大數目

這題一開始讀錯題了，以為是最大化連通分量中的最大值。但實際上是最大化連通分量元素和。還是跟以前一樣套路，分開深搜維護最大值即可。

class Solution {boolean[] vis;int m,n;int[][] dirs = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};public int findMaxFish(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m*n];int max = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(!vis[i*n+j]&&grid[i][j]>0){max = Math.max(max,dfs(grid,i,j));}}}return max;}private int dfs(int[][] g,int x,int y){if(vis[x*n+y]){return 0;}vis[x*n+y]=true;int nx,ny;int cnt = g[x][y];for (int[] dir : dirs) {nx = x+dir[0];ny = y+dir[1];if(indexValid(nx,ny)&&g[nx][ny]>0){cnt += dfs(g,nx,ny);}}return cnt;}private boolean indexValid(int x,int y){return x>=0 && x<m && y>=0 && y<n;}
}

1.7. LC 1020 飛地的數量

這道題雖然A了但是思路比較差。我是直接深搜，然后打一個標記位置，深搜到邊界給標記位置置true，然后深搜返回的是連通塊的大小。如果標記位為false說明連通塊沒有到邊界，這樣就可以累加。

但是更好的思路是，直接從邊界深搜，把能抵達的1全部標記出來，剩下沒標記的都是要求的。

import java.util.Arrays;class Solution {boolean[][] vis;int[][] directions = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};int m,n;boolean flag;public int numEnclaves(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m][n];int sum = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(grid[i][j]==1&&!vis[i][j]){flag = false;int tmp = dfs(grid, i, j);if(!flag){sum+=tmp;}}}}return sum;}private int dfs(int[][] grid,int x,int y){if(vis[x][y]||grid[x][y]==0){return 0;}vis[x][y] = true;if(x==0||x==m-1||y==0||y==n-1){flag = true;}int nx,ny,sum;sum = 0;for (int[] direction : directions) {nx = x+direction[0];ny = y+direction[1];if(isValid(nx,ny)){sum += dfs(grid,nx,ny);}}return sum+1;}private boolean isValid(int x,int y){return x>=0 && x<m && y>=0 &&y<n;}
}

這個是我的。

class Solution {public int numEnclaves(int[][] grid) {int m = grid.length;int n = grid[0].length;for(int i = 0; i < m; i ++){if(grid[i][0] == 1) dfs(grid, i, 0, m, n);if(grid[i][n - 1] == 1) dfs(grid, i, n - 1, m , n);}for(int i = 0; i < n; i ++){if(grid[0][i] == 1) dfs(grid, 0, i, m, n);if(grid[m - 1][i] == 1) dfs(grid, m - 1, i, m ,n);}int res = 0;for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){if(grid[i][j] == 1){res ++;}}}return res;}public void dfs(int[][] grid, int i, int j, int m, int n){if(i < 0 || j < 0 || i >= m || j >= n) return;if(grid[i][j] == 0) return;grid[i][j] = 0;dfs(grid, i + 1, j, m, n);dfs(grid, i - 1, j, m ,n);dfs(grid, i, j + 1, m, n);dfs(grid, i, j - 1, m, n);}
}

更好的思路。

1.8. LC 1254 統計封閉島嶼的數目

可以這么想，如果一個0的連通塊存在元素在邊界上，那么就不是封閉島嶼，反過來就是。這樣深搜的時候檢查是否到達過邊界。如果沒有到達過的話增1就可以了。

import java.util.Arrays;class Solution {int m,n;boolean[] vis;int[][] directions = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};public int closedIsland(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m*n];Arrays.fill(vis,false);int ans = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(!vis[i*n+j]&&grid[i][j]!=1){if(!dfs(grid,i,j)){ans++;}}}}return ans;}private boolean isOnEdge(int x,int y){return x==0||y==0||x==m-1||y==n-1;}private boolean isValid(int x,int y){return x>=0 && x<m && y>=0 && y<n;}private boolean dfs(int[][] grid,int x,int y){if(grid[x][y]==1||vis[x*n+y]){return false;}vis[x*n+y] = true;int nx,ny;boolean flag = isOnEdge(x,y);for (int[] direction : directions) {nx = x+direction[0];ny = y+direction[1];if(isValid(nx,ny)){flag|=dfs(grid,nx,ny);}}return flag;}
}

1.9. LC 130 被圍繞的區域

這題別和上題一樣判斷是否連通塊有邊界元素，因為判完再染之前深搜的可能漏染了。

可以這樣，先從邊界深搜，把邊界上的O所在的連通塊全訪問掉。這樣剩下的就是內部的了（被圍繞的O），然后深搜內部染色就行。

class Solution {int m,n;boolean[][] vis;int[][] directions = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};public void solve(char[][] board) {m = board.length;n = board[0].length;vis = new boolean[m][n];for (int i = 0; i < n; i++) {if(board[0][i]=='O'&&!vis[0][i]){dfs(board,0,i,true);}}for (int i = 0; i < n; i++) {if(board[m-1][i]=='O'&&!vis[m-1][i]){dfs(board,m-1,i,true);}}for (int i = 0; i < m; i++) {if(board[i][0]=='O'&&!vis[i][0]){dfs(board,i,0,true);}}for (int i = 0; i < m; i++) {if(board[i][n-1]=='O'&&!vis[i][n-1]){dfs(board,i,n-1,true);}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(board[i][j]=='O'&&!vis[i][j]){dfs(board,i,j,false);}}}}private void dfs(char[][] g,int x,int y,boolean OnEdge){if(g[x][y]=='X'||vis[x][y]){return;}vis[x][y] = true;int nx,ny;for (int[] direction : directions) {nx = x+direction[0];ny = y+direction[1];if(isValid(nx,ny)){dfs(g,nx,ny,OnEdge);}}if(!OnEdge){g[x][y] ='X';}}private boolean isValid(int x,int y){return x>=0 && x<m && y>=0 && y<n;}
}

1.10. LC 1391 檢查網格中是否存在有效路徑

這題很惡心。首先要選擇不同形狀街道的行走方向，比如第一個街道既可以從左往右，又可以從右到左；第二得保證下一個格子的街道形狀能夠對接的上這個各自的街道形狀。比如1可以拼接5但不能拼接6。這兩個條件我打表了兩個巨繁的數組。其中directions[i]是一個二維數組，表示值為i+1的單元格的行走方向，每個行走方向都是一個二維向量。accept[i]也是一個二維數組，表示值為i+1的單元格可以接受的街道形狀的對應id-1。

class Solution {int m,n;int[][][] directions = new int[][][]{{{0,-1},{0,1}},{{-1,0},{1,0}},{{0,-1},{1,0}},{{0,1},{1,0}},{{0,-1},{-1,0}},{{0,1},{-1,0}}};int[][][] accept = new int[][][]{{{0,3,5},{0,2,4}},{{1,2,3},{1,4,5}},{{0,3,5},{1,4,5}},{{0,2,4},{1,4,5}},{{0,3,5},{1,2,3}},{{0,2,4},{1,2,3}}};boolean[][] vis;public boolean hasValidPath(int[][] grid) {m = grid.length;n = grid[0].length;vis = new boolean[m][n];return dfs(grid,0,0);}private boolean dfs(int[][] grid,int x,int y){if(x==m-1 && y==n-1){return true;}vis[x][y] = true;int nx,ny;int way = grid[x][y]-1;boolean flag = false;for (int i = 0; i < directions[way].length; i++) {nx = x+directions[way][i][0];ny = y+directions[way][i][1];if(isValid(nx,ny)&&!vis[nx][ny]){if(contains(accept[way][i],grid[nx][ny]-1)){flag|=dfs(grid,nx,ny);}}}return flag;}private boolean isValid(int x,int y){return x>=0 && x<m && y>=0 && y<n;}private boolean contains(int[] arr,int target){for (int i : arr) {if(i==target){return true;}}return false;}
}

其實還好，O(mn)的。就是寫起來要有一堆規則，很惡心。