リーコード島問題関連

島の数

200. 島の数
1'と'0'からなる2次元格子が与えられたとき、その格子に含まれる島の数を計算せよ。
島は常に水に囲まれており、隣接する陸地を水平または垂直に結合することによってのみ形成される。
さらに、グリッドの4辺はすべて水に囲まれていると仮定できる。
例1:
 :
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
 : 1
例2:
 :
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
 : 3
 : 各島は、隣接する陸地を水平方向および/または垂直方向に結合することによってのみ形成することができる。

class Solution {
 int res = 0;
 public int numIslands(char[][] grid) {
 if (grid == null || grid.length == 0)
 return 0;
 for (int i = 0; i < grid.length; i++) {
 for (int j = 0; j < grid[0].length; j++) {
 if (grid[i][j] == '1') {
 res++;
 dfs(grid, i, j);
 }
 }
 }
 return res;
 }
 private void dfs(char[][] grid, int i, int j) {
 if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0')
 return;
 grid[i][j] = '0';
 dfs(grid, i + 1, j);
 dfs(grid, i - 1, j);
 dfs(grid, i, j + 1);
 dfs(grid, i, j - 1);
 }
}

島の最大サイズ

695. 島の最大面積
いくつかの0と1を含む空でない2次元配列格子が与えられる．
島は隣り合う1の組み合わせである。"隣り合う "ということは、2つの1が水平または垂直に隣接していなければならない。グリッドの4つの辺はすべて0に囲まれていると考えてよい。
与えられた2次元配列の中で、島の最大の面積を求める。
 
例1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
島は水平または垂直の4方向にしか1を含むことができないので、答えは11であってはならない。
例2:
[[0,0,0,0,0,0,0,0]]
上の行列の場合、0を返す。

class Solution {
 int res = 0;
 public int maxAreaOfIsland(int[][] grid) {
 if (grid == null || grid.length == 0)
 return 0;
 for (int i = 0; i < grid.length; i++) {
 for (int j = 0; j < grid[0].length; j++) {
 res = Math.max(res, dfs(grid, i, j));
 }
 }
 return res;
 }
 private int dfs(int[][] grid, int i, int j) {
 if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0)
 return 0;
 int count = 1;
 grid[i][j] = 0;
 count += dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
 return count;
 }
}