LeetCode关于二维数组BFS和DFS的问题
关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
LeetCode题目：317. Shortest Distance from All Buildings
You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
- Each 0 marks an empty land which you can pass by freely.
- Each 1 marks a building which you cannot pass through.
- Each 2 marks an obstacle which you cannot pass through.
For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):
1 - 0 - 2 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.
Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.
class Solution {
public int shortestDistance(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0) return -1;
int row = grid.length;
int col = grid[0].length;
// record1记录每一个empty land能联通到多少个building
int[][] record1 = new int[row][col];
// record2记录每一个empty land到能够联通到的building的距离之和
int[][] record2 = new int[row][col];
// building数目
int buildingCount = 0;
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
// 找到每一个building，做BFS，计算其到每一个empty land的距离
if (grid[r][c] == 1) {
// building数目
buildingCount++;
boolean[][] visited = new boolean[row][col];
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[]{r, c});
int distance = 0;
while (!queue.isEmpty()) {
int size = queue.size();
// 按层次的BFS
for (int i = 0; i < size; i++) {
int[] node = queue.poll();
int x = node[0];
int y = node[1];
// record1记录每一个empty land能联通到多少个building
record1[x][y]++;
// record2记录每一个empty land到能够联通到的building的距离之和
record2[x][y]+=distance;
int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(int[] d : dir) {
int nx = x + d[0];
int ny = y + d[1];
if(nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == 0 && !visited[nx][ny]) {
queue.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
distance++;
}
}
}
}
int result = Integer.MAX_VALUE;
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
// 遍历每一个empty land，如果它能联通到所有的building
if (grid[r][c] == 0 && record1[r][c] == buildingCount) {
result = Math.min(result, record2[r][c]);
}
}
}
return result == Integer.MAX_VALUE ? -1 : result;
}
}
LeetCode题目：417. Pacific Atlantic Water Flow
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
- The order of returned grid coordinates does not matter.
- Both m and n are less than 150.
Example:
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
class Solution {
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> result = new ArrayList<int[]>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;
int m = matrix.length;
int n = matrix[0].length;
// pacific[i][j]表示(i, j)能否得到pacific
boolean[][] pacific = new boolean[m][n];
// atlantic[i][j]表示(i, j)能否得到atlantic
boolean[][] atlantic = new boolean[m][n];
for (int i = 0; i < m; i++) {
// 从左边开始搜索是否可以到达pacific
dfs(matrix, pacific, i, 0, m, n);
// 从右边开始搜索是否可以到达atlantic
dfs(matrix, atlantic, i, n - 1, m, n);
}
for (int i = 0; i < n; i++) {
// 从上边开始搜索是否可以到达pacific
dfs(matrix, pacific, 0, i, m, n);
// 从下边开始搜索是否可以到达atlantic
dfs(matrix, atlantic, m - 1, i, m, n);
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(pacific[i][j] == true && atlantic[i][j] == true) {
result.add(new int[]{i, j});
}
}
}
return result;
}
public void dfs(int[][] matrix, boolean[][] canArrive, int x, int y, int m, int n) {
// canArrive也起到了visited数组的作用
canArrive[x][y] = true;
int[] directionX = new int[]{-1, 1, 0, 0};
int[] directionY = new int[]{0, 0, -1, 1};
// 遍历4个方向
for(int i = 0; i < 4; i++) {
int newX = x + directionX[i];
int newY = y + directionY[i];
if(newX >= 0 && newX < m && newY >= 0 && newY < n
&& !canArrive[newX][newY]
&& matrix[newX][newY] >= matrix[x][y]) {
dfs(matrix, canArrive, newX, newY, m, n);
}
}
}
}
