做摄影网站的目的是什么/搜狐财经峰会
leetcode 1162. 地图分析
BFS在网格中的应用
如图，1是岛屿，2是海鲜，则可以通过广度搜索，最大路径是4
与树的BFS区别如下：
1、tree只有1个root，而图可以有多个源点，所以首先需要把多个源点都入队。
2、tree是有向的因此不需要标记是否访问过，而对于无向图来说，必须得标记是否访问过。并且为了防止某个节点多次入队，需要在入队之前就将其设置成已访问。
使用BFS解题
代码如下，代码比较多，等下一步步讲解
class Solution {static int[] dx = {-1, 0, 1, 0};static int[] dy = {0, 1, 0, -1};int n;int[][] grid;public int maxDistance(int[][] grid) {this.n = grid.length;this.grid = grid;int ans = -1;for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 0) {ans = Math.max(ans, findNearestLand(i, j));}}}return ans;}public int findNearestLand(int x, int y) {boolean[][] vis = new boolean[n][n];Queue<int[]> queue = new LinkedList<int[]>();queue.offer(new int[]{x, y, 0});vis[x][y] = true;while (!queue.isEmpty()) {int[] f = queue.poll();for (int i = 0; i < 4; ++i) {int nx = f[0] + dx[i], ny = f[1] + dy[i];if (!(nx >= 0 && nx < n && ny >= 0 && ny < n)) {continue;}if (!vis[nx][ny]) {queue.offer(new int[]{nx, ny, f[2] + 1});vis[nx][ny] = true;if (grid[nx][ny] == 1) {return f[2] + 1;}}}}return -1;}
}
从坐标上来说，左上角开始为(0,0)，我们需要知道某个坐标(x,y)上下左右的位置，就需要四个方向左(x-1,y)，右(x+1,y)，上(x,y-1)，下(x,y+1)
回到代码中，因此需要先声明两个数组，遍历的时候就能去遍历上下左右四个新坐标了
这里的nx和ny就是走过一步后的新坐标。如果该坐标不在网格内，跳过当前循环，否则，塞入队列中，并且count数+1，这里的count数就是入队列中数组的第三个值，用来算最大距离的，而前两个值存的是x和y
前面说过，对于无向图，必须得标记是否访问过。并且为了防止某个节点多次入队，需要在入队之前就将其设置成已访问。更通俗的讲，就是已经走过一遍的坐标就不要再走一次了。关于标记，方法如下
最后返回最大距离
再看官方图解的时候，就很清楚了
时间复杂度
遍历会有四次循环，所以时间复杂度基本会比较高，为O(n4)，官方还有其他解法，这里只介绍bfs在最短路径中的解法