# 1. 827. Maximum artificial island (depth first)

On a two-dimensional map, 0 represents the ocean and 1 represents the land. We can only change a grid of 0 oceans into a land at most.

What is the area of the largest island on the map after reclamation? (1 islands connected in the upper, lower, left and right directions)

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Interpretation: Turn a grid 0 into a grid 1, and eventually connect the two islands to an island of 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the grid 0 to 1 and expand the island area to 4.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: No 0 can make us 1, and the area is still 4.

Explain:

1 <= grid.length = grid.length <= 50
0 <= grid[i][j] <= 1

```public int largestIsland(int[][] grid) {
if (grid == null || grid.length == 0)
return 0;

int max = 0;
int row = grid.length;
int col = grid.length;
//There must be this, in order to solve this situation {{1}}
boolean hasZero = false;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 0) {
hasZero = true;
grid[i][j] = 1;
int cur = dfs(grid, i, j, row, col, new boolean[row][col]);
if (cur == row * col)
return cur;

if (cur > max) {
max = cur;
}
grid[i][j] = 0;
}
}
}
return hasZero ? max : row * col;
}

private int dfs(int[][] grid, int i, int j, int row, int col, boolean[][] booleans) {
//In this case, return 0
if (i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == 0 || booleans[i][j])
return 0;

booleans[i][j] = true;
return 1 + dfs(grid, i + 1, j, row, col, booleans) + dfs(grid, i - 1, j, row, col, booleans) + dfs(grid, i, j + 1, row, col, booleans) + dfs(grid, i, j - 1, row, col, booleans);
}
```

# 2. Beijing East 2019 Spring Call Written Examination (Fire, Depth First) Train of thought:
Find the left and right subtrees of the root node, and the number of nodes is the most.

```//Depth first
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String nStr = sc.nextLine();
int n = Integer.parseInt(nStr);
int[][] edges = new int[n];
for (int i = 0; i < n - 1; i++) {
String str = sc.nextLine();
String[] strings = str.split(" ");
edges[i] = Integer.parseInt(strings);
edges[i] = Integer.parseInt(strings);
}

HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>();
for (int i = 0; i < n; i++) {
if (hashMap.containsKey(edges[i])) {
} else {
ArrayList<Integer> arrayList = new ArrayList<>();
hashMap.put(edges[i], arrayList);
}
}
ArrayList<Integer> arrayList = hashMap.get(1);
int res = 0;
for (int i : arrayList) {
int temp = dfs(hashMap, i);
if (temp > res) {
res = temp;
}
}
System.out.println(res);
}
}

private static int dfs(HashMap<Integer, ArrayList<Integer>> hashMap, int num) {
int count = 1;
if (hashMap.get(num) == null)
return count;
for (int i : hashMap.get(num)) {
count += dfs(hashMap, i);
}
return count;
}
```

# 3,

Given a non-spatial two-dimensional array grid containing some zeros and ones, an island is a combination of four directions (horizontal or vertical) of one (representing land). You can assume that the four edges of a two-dimensional matrix are surrounded by water.

Find the largest island area in a given two-dimensional array. (If there are no islands, the return area is 0. )

Example 1: For the given matrix above, return 6. Note that the answer should not be 11, because the islands can only contain `1'in four horizontal or vertical directions.

Example 2:

[[0,0,0,0,0,0,0,0]]

For the given matrix above, return 0.

Note: The length and width of a given matrix grid are not more than 50.

Code:

Note: After traversing grid[i][j]=1, make grid[i][j]=-1

```public int maxAreaOfIsland(int[][] grid) {
int row=grid.length;
int col=grid.length;

int max=0;

for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j]==1){
int cur=dfs(grid,i,j,row,col);
if(cur==row*col){
return cur;
}
if(cur>max){
max=cur;
}
}
}
}
return max;
}

private int dfs(int[][] grid, int i, int j, int row, int col) {
if(i<0||j<0||i>=row||j>=col||grid[i][j]==0||grid[i][j]==-1)
return 0;

grid[i][j]=-1;
return 1+dfs(grid,i+1,j,row,col)+dfs(grid,i-1,j,row,col)+dfs(grid,i,j+1,row,col)+dfs(grid,i,j-1,row,col);
}
```

Keywords: Spring

Added by igorlopez on Sun, 19 May 2019 14:07:39 +0300