?思路1： DFS，對(duì)于每個(gè)門進(jìn)行一次DFS搜索，記錄每個(gè)位置對(duì)每個(gè)門的距離，當(dāng)有更小距離的門時(shí)更新這個(gè)數(shù)值

public void WallsAndGates(int[][] rooms) {for (int i = 0; i < rooms.GetLength(0); i++){for (int j = 0; j < rooms[i].GetLength(0); j++){if (rooms[i][j] == 0){DFS(rooms, i, j, 0);}}} }void DFS(int[][] rooms, int x, int y, int val){if (x < 0 || x >= rooms.GetLength(0))return;if (y < 0 || y >= rooms[x].GetLength(0))return;if (rooms[x][y] < val)return;rooms[x][y] = val;DFS(rooms, x + 1, y, val + 1);DFS(rooms, x, y + 1, val + 1);DFS(rooms, x - 1, y, val + 1);DFS(rooms, x, y - 1, val + 1);}

?思路2： 多源BFS，先把每個(gè)門都?jí)喝腙?duì)列中，然后進(jìn)行BFS搜索，BFS搜索保證了每個(gè)位置只需要遍歷到一次，第一次搜索到時(shí)一定是最短距離，因此這種算法對(duì)于大量數(shù)據(jù)時(shí)肯定會(huì)更優(yōu)秀

private List<int[]> directions = new List<int[]>(){new int[]{1, 0}, new int[]{-1, 0},new int[]{0, 1},new int[]{0, -1}}; private const int INF = 2147483647; public void WallsAndGates(int[][] rooms){Queue<int[]> queue = new Queue<int[]>();int?maxRow?=?rooms.GetLength(0);if(maxRow == 0)return;int?maxCow?=?rooms[0].Length;for (int i = 0; i < maxRow; i++){for (int j = 0; j < maxCow; j++){if (rooms[i][j] == 0){queue.Enqueue(new int[]{i,j});}}}while(queue.Count > 0){int[] tile = queue.Dequeue();for(int i = 0; i < directions.Count; i++){int x = tile[0] + directions[i][0];int y = tile[1] + directions[i][1];if(x < 0 || x > maxRow - 1 || y < 0 || y > maxCow - 1 || rooms[x][y] != INF){continue;}rooms[x][y] = rooms[tile[0]][tile[1]] + 1;queue.Enqueue(new int[]{x, y});}} } }

判題的結(jié)果是兩者時(shí)間差不多太多，都在340ms左右，但是明顯在數(shù)據(jù)量大的情況下應(yīng)該是多源BFS算法更優(yōu)秀很多。多源BFS最快是328ms，第一次的704ms是因?yàn)橛昧薒ist沒有Queue

?

總結(jié)

以上是生活随笔為你收集整理的LeetCode 286. 墙与门 多源BFS和DFS的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。