int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1, 0}};
public int numIslands(char[][] grid) {
}
void dfs(char[][] grid, int x, int y){
for (int[] dir : dirs){
dfs(grid, x+dir[0], y+dir[1]);
}
}
首先定义dirs 搜索的方向，新建dfs方法，深度搜索每一个方向，需要之后增加推出条件。
200. 岛屿数量思路：整个网格搜索，找到一个1 就dfs把所有的1都找出来变成0，这样就是一个岛屿。在dfs的时候，下个搜索对象只能是1不然就结束。
class Solution {
int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1, 0}};
public int numIslands(char[][] grid) {
int res = 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;
}
void dfs(char[][] grid, int x, int y){
grid[x][y] = '0';
for (int[] dir : dirs){
int next_x = x+dir[0];
int next_y = y+dir[1];
if (next_x >= 0 && next_x < grid.length && next_y >= 0 && next_y < grid[0].length && grid[next_x][next_y] == '1' ){
dfs(grid, next_x, next_y);
}
}
}
}
463. 岛屿的周长
思路：题目说只有一个岛屿，所以找到一个1就可以直接dfs return就好了。dfs中搜索，如果碰到边界或者是0就周长+1，如果是0就继续搜索。
class Solution {
int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
int count = 0;
public int islandPerimeter(int[][] grid) {
for (int i = 0; i < grid.length; i++){
for (int j = 0; j < grid[0].length; j++){
if (grid[i][j] == 1){
dfs(grid, i, j);
return count;
}
}
}
return -1;
}
void dfs(int[][] grid, int x, int y){
grid[x][y] = 2;
for (int[] dir : dirs){
int next_x = x+dir[0];
int next_y = y+dir[1];
if (next_x < 0 || next_x >= grid.length || next_y < 0 || next_y >= grid[0].length
|| grid[next_x][next_y] == 0){
count++;
continue;
}
if (grid[next_x][next_y] == 1) dfs(grid, next_x, next_y);
}
}
}
695. 岛屿的最大面积
思路：全局遍历grid，找到1就dfs，一次找出所有连接的土地，返回面积。
class Solution {
int[][] dir = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
public int maxAreaOfIsland(int[][] grid) {
int res = 0;
for (int i = 0; i < grid.length; i++){
for (int j = 0; j < grid[0].length; j++){
if (grid[i][j] == 1){
res = Math.max(res, dfs(grid, i, j));
}
}
}
return res;
}
int dfs(int[][] grid, int x, int y){
int temp = 0;
grid[x][y] = 0;
temp++;
for (int[] move : dir){
int next_x = x + move[0];
int next_y = y + move[1];
if (next_x >= 0 && next_x < grid.length && next_y >= 0 && next_y
934. 最短的桥
思路：先一遍dfs遍历其中一个岛，用queue记录下每个点的坐标，让后根据坐标一层一层向外找。
class Solution {
int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1, 0}};
public int shortestBridge(int[][] grid) {
Queue queue = new linkedList<>();
boolean visited = false;
for (int i = 0; i < grid.length; i++){
for (int j = 0; j < grid[0].length; j++){
if (grid[i][j] == 1){
visited = true;
dfs_first(grid, i, j, queue);
break;
}
}
if (visited) break;
}
int count = 0;
while (!queue.isEmpty()){
int size = queue.size();
for (int i = 0; i < size; i++){
int[] candidate = queue.poll();
for (int[] dir : dirs){
int next_x = candidate[0] + dir[0];
int next_y = candidate[1] + dir[1];
if (next_x >= 0 && next_x < grid.length && next_y >= 0
&& next_y < grid[0].length){
if (grid[next_x][next_y] == 1 ){
return count;
}
else if (grid[next_x][next_y] == 0){
grid[next_x][next_y] = 2;
queue.offer(new int[]{next_x, next_y});
}
}
}
}
count++;
}
return -1;
}
void dfs_first(int[][] grid, int x, int y, Queue queue){
grid[x][y] = 2;
queue.offer(new int[]{x,y});
for (int[] dir : dirs){
int next_x = x+dir[0];
int next_y = y+dir[1];
if (next_x >= 0 && next_x < grid.length && next_y >= 0 && next_y < grid[0].length
&& grid[next_x][next_y] == 1 ){
dfs_first(grid, next_x, next_y, queue);
}
}
}
}
827. 最大人工岛
思路一：把每一个0 先当成1 在用dfs 遍历返回面积，取最大面积。（超时）
class Solution {
int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1, 0}};
public int largestIsland(int[][] grid) {
int res = 0;
for (int i = 0; i < grid.length; i++){
for (int j = 0; j < grid[0].length; j++){
if (grid[i][j] == 0){
grid[i][j] = 1;
res = Math.max(res, dfs(grid, i, j, new boolean[grid.length][grid[0].length]));
grid[i][j] = 0;
}
}
}
return res == 0 ? grid.length*grid[0].length : res;
}
int dfs(int[][] grid, int x, int y, boolean[][] visited){
visited[x][y] = true;
int ans = 0;
for (int[] dir : dirs){
int next_x = x+dir[0];
int next_y = y+dir[1];
if (next_x >= 0 && next_x < grid.length && next_y >= 0 && next_y < grid[0].length
&& grid[next_x][next_y] == 1 && ! visited[next_x][next_y]){
ans += dfs(grid, next_x, next_y, visited);
}
}
return ans+1;
}
}
思路二 寻找出每个岛屿,并讲同一岛屿用同一个value标记，存储每个岛屿的面积。然后从0开始查找找出能连接的最大的面积。
class Solution {
public int largestIsland(int[][] grid) {
int value = 2; // 岛屿编号
Map islandAreas = new HashMap<>(); // 岛屿编号 -> 岛屿面积的 map
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
int a = area(grid, r, c, value);
islandAreas.put(value, a);
value++;
}
}
}
int res = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
// 依次尝试填海
int ta = thisArea(grid, r, c, islandAreas);
res = Math.max(res, ta);
}
}
return res;
}
// 把 (r, c) 填海之后，最大的岛屿面积
int thisArea(int[][] grid, int r, int c, Map islandAreas) {
if (grid[r][c] != 0) {
return islandAreas.get(grid[r][c]);
}
int res = 0;
Set adjs = new HashSet<>();
if (inArea(grid, r-1, c) && grid[r-1][c] > 0) {
adjs.add(grid[r-1][c]);
}
if (inArea(grid, r+1, c) && grid[r+1][c] > 0) {
adjs.add(grid[r+1][c]);
}
if (inArea(grid, r, c-1) && grid[r][c-1] > 0) {
adjs.add(grid[r][c-1]);
}
if (inArea(grid, r, c+1) && grid[r][c+1] > 0) {
adjs.add(grid[r][c+1]);
}
for (int adj : adjs) {
System.out.println("adj = " + adj);
res += islandAreas.get(adj);
}
return res + 1;
}
// value 表示当前岛屿编号
int area(int[][] grid, int r, int c, int value) {
if (!inArea(grid, r, c)) {
return 0;
}
if (grid[r][c] != 1) {
return 0;
}
grid[r][c] = value;
return 1 + area(grid, r - 1, c, value)
+ area(grid, r + 1, c, value)
+ area(grid, r, c - 1, value)
+ area(grid, r, c + 1, value);
}
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
}
