2023-05-13：你現(xiàn)在手里有一份大小為 n x n 的 網(wǎng)格 grid,

上面的每個(gè) 單元格 都用 0 和 1 標(biāo)記好了其中 0 代表海洋，1 代表陸地。

請(qǐng)你找出一個(gè)海洋單元格，這個(gè)海洋單元格到離它最近的陸地單元格的距離是最大的,

并返回該距離。如果網(wǎng)格上只有陸地或者海洋，請(qǐng)返回 -1。

我們這里說(shuō)的距離是「曼哈頓距離」（ Manhattan Distance）：

(x0, y0) 和 (x1, y1) 這兩個(gè)單元格之間的距離是 |x0 - x1| + |y0 - y1| 。

輸入：grid = [[1,0,0],[0,0,0],[0,0,0]]。

輸出：4。

答案2023-05-13：

大體步驟如下：

1.定義變量：

• ??聲明一個(gè)二維整數(shù)數(shù)組grid表示網(wǎng)格，以及整數(shù)變量n和m表示網(wǎng)格的行數(shù)和列數(shù)；

• ??聲明一個(gè)二維布爾數(shù)組visited，用于記錄每個(gè)單元格是否被訪問(wèn)過(guò)；

• ??聲明一個(gè)二維整數(shù)數(shù)組queue，用于存儲(chǔ)隊(duì)列中的每個(gè)元素；

• ??聲明整數(shù)變量l和r，分別表示隊(duì)列的左右端點(diǎn)；

• ??聲明整數(shù)變量find，統(tǒng)計(jì)已經(jīng)找到的海洋的數(shù)量；

• ??聲明整數(shù)變量seas，統(tǒng)計(jì)海洋的總數(shù)量；

• ??聲明整數(shù)變量distance，表示最深能找到的海洋層數(shù)，初始化為-1。

2.初始化變量：

• ??將l、r、find、seas和distance全部初始化為0或-1，將visited數(shù)組全部設(shè)為false；

• ??遍歷整個(gè)網(wǎng)格，對(duì)于每個(gè)陸地單元格，將其標(biāo)記為已訪問(wèn)，并將其加入隊(duì)列中；對(duì)于每個(gè)海洋單元格，將seas增加1。

3.進(jìn)行BFS搜索：

• ??當(dāng)隊(duì)列不為空時(shí)，取出隊(duì)列中所有元素進(jìn)行處理，直到找到所有的海洋單元格；

• ??對(duì)于每個(gè)隊(duì)列元素，將其四周的海洋單元格加入隊(duì)列中，并標(biāo)記為已訪問(wèn)；同時(shí)統(tǒng)計(jì)找到的海洋單元格數(shù)量，并將distance加1。

4.返回結(jié)果：

• ??如果沒(méi)有找到任何海洋或者陸地，則返回-1；

• ??否則，返回distance。

時(shí)間復(fù)雜度：

• ??初始化visited數(shù)組、queue數(shù)組和一些變量的時(shí)間復(fù)雜度是O(n^2)，其中n為網(wǎng)格邊長(zhǎng)；

• ??遍歷整個(gè)網(wǎng)格的時(shí)間復(fù)雜度也是O(n^2)；

• ??BFS搜索的時(shí)間復(fù)雜度最壞情況下是O(n^2)，因?yàn)樽疃嘈枰闅v整個(gè)網(wǎng)格。

因此，總的時(shí)間復(fù)雜度是O(n^2)。

空間復(fù)雜度：

• ??visited數(shù)組的空間復(fù)雜度是O(n^2)；

• ??queue數(shù)組的空間復(fù)雜度是O(n^2)；

• ??其他變量占用常數(shù)空間。

因此，總的空間復(fù)雜度是O(n^2)。

go語(yǔ)言完整代碼如下：

package?main

var?queue?[10000][2]int
var?l?int
var?r?int
var?visited?[100][100]bool
var?find?int

func?maxDistance(grid?[][]int)?int?{
????//?清空變量
????l?=?0
????r?=?0
????find?=?0
????n?:=?len(grid)
????m?:=?len(grid[0])
????//?清空visited
????for?i?:=?0;?i?<?n;?i++?{
????????for?j?:=?0;?j?<?m;?j++?{
????????????visited[i][j]?=?false
????????}
????}
????//?大體思路?:
????//?1)?先把所有的陸地加入隊(duì)列，并且統(tǒng)計(jì)一共有多少海洋
????seas?:=?0
????for?i?:=?0;?i?<?n;?i++?{
????????for?j?:=?0;?j?<?m;?j++?{
????????????if?grid[i][j]?==?1?{
????????????????visited[i][j]?=?true
????????????????queue[r][0]?=?i
????????????????queue[r][1]?=?j
????????????????r++
????????????}?else?{
????????????????seas++
????????????}
????????}
????}
????//?2)?從陸地開(kāi)始廣播出去(bfs)，每一塊陸地的上、下、左、右所能找到的海洋都是第一層海洋
????//?3)?第一層海洋繼續(xù)bfs，每一塊海洋的上、下、左、右所能找到的海洋都是第二層海洋
????//?4)?第二層海洋繼續(xù)bfs，每一塊海洋的上、下、左、右所能找到的海洋都是第三層海洋
????//?...
????//?也就是說(shuō)，以陸地做起點(diǎn)，每一層bfs都只找海洋！
????//?看看最深能找到多少層海洋
????distance?:=?-1?????????????//?這個(gè)變量就是最深的海洋層數(shù)
????for?l?<?r?&&?find?<?seas?{?//?find?<?seas說(shuō)明所有的海洋塊沒(méi)有找全，繼續(xù)找！
????????size?:=?r?-?l
????????for?i?:=?0;?i?<?size?&&?find?<?seas;?i++?{
????????????row?:=?queue[l][0]
????????????col?:=?queue[l][1]
????????????add(row-1,?col,?n,?m,?grid)
????????????add(row+1,?col,?n,?m,?grid)
????????????add(row,?col-1,?n,?m,?grid)
????????????add(row,?col+1,?n,?m,?grid)
????????????l++
????????}
????????distance++
????}
????if?find?==?0?{
????????return?-1
????}
????return?distance?+?1
}

func?add(i?int,?j?int,?n?int,?m?int,?grid?[][]int)?{
????if?i?>=?0?&&?i?<?n?&&?j?>=?0?&&?j?<?m?&&?grid[i][j]?==?0?&&?!visited[i][j]?{
????????find++
????????visited[i][j]?=?true
????????queue[r][0]?=?i
????????queue[r][1]?=?j
????????r++
????}
}

func?main()?{
????grid?:=?[][]int{{1,?0,?1},?{0,?0,?0},?{1,?0,?1}}
????result?:=?maxDistance(grid)
????println(result)
????grid?=?[][]int{{1,?0,?0},?{0,?0,?0},?{0,?0,?0}}
????result?=?maxDistance(grid)
????println(result)
}


rust語(yǔ)言完整代碼如下：

static?mut?QUEUE:?[[i32;?2];?10000]?=?[[0;?2];?10000];
static?mut?L:?usize?=?0;
static?mut?R:?usize?=?0;
static?mut?VISITED:?[[bool;?100];?100]?=?[[false;?100];?100];
static?mut?FIND:?i32?=?0;

fn?main()?{
????let?grid?=?vec![vec![1,?0,?1],?vec![0,?0,?0],?vec![1,?0,?1]];
????unsafe?{
????????let?ans?=?max_distance(grid);
????????println!("ans?=?{}",?ans);
????}
????let?grid?=?vec![vec![1,?0,?0],?vec![0,?0,?0],?vec![0,?0,?0]];
????unsafe?{
????????let?ans?=?max_distance(grid);
????????println!("ans?=?{}",?ans);
????}
}

unsafe?fn?max_distance(grid:?Vec<Vec<i32>>)?->?i32?{
????//?清空變量
????//?只要l?=?0，r?=?0，隊(duì)列就算被清空了
????L?=?0;
????R?=?0;
????FIND?=?0;
????let?n?=?grid.len();
????let?m?=?grid[0].len();
????//?清空visited
????for?i?in?0..n?{
????????for?j?in?0..m?{
????????????VISITED[i][j]?=?false;
????????}
????}

????//?初始化隊(duì)列
????let?mut?queue:?[[i32;?2];?10000]?=?[[0;?2];?10000];

????//?大體思路?:
????//?1)?先把所有的陸地加入隊(duì)列，并且統(tǒng)計(jì)一共有多少海洋
????let?mut?seas?=?0;
????for?i?in?0..n?{
????????for?j?in?0..m?{
????????????if?grid[i][j]?==?1?{
????????????????VISITED[i][j]?=?true;
????????????????queue[R][0]?=?i?as?i32;
????????????????queue[R][1]?=?j?as?i32;
????????????????R?+=?1;
????????????}?else?{
????????????????seas?+=?1;
????????????}
????????}
????}

????//?2)?從陸地開(kāi)始廣播出去(bfs)，每一塊陸地的上、下、左、右所能找到的海洋都是第一層海洋
????//?3)?第一層海洋繼續(xù)bfs，每一塊海洋的上、下、左、右所能找到的海洋都是第二層海洋
????//?4)?第二層海洋繼續(xù)bfs，每一塊海洋的上、下、左、右所能找到的海洋都是第三層海洋
????//?...
????//?也就是說(shuō)，以陸地做起點(diǎn)，每一層bfs都只找海洋！
????//?看看最深能找到多少層海洋
????let?mut?distance?=?0;?//?這個(gè)變量就是最深的海洋層數(shù)
????while?L?<?R?&&?FIND?<?seas?{
????????//?find?<?seas說(shuō)明所有的海洋塊沒(méi)有找全，繼續(xù)找！
????????let?size?=?R?-?L;
????????for?i?in?0..size?{
????????????if?FIND?>=?seas?{
????????????????break;
????????????}
????????????let?row?=?queue[L][0];
????????????let?col?=?queue[L][1];
????????????add(row?-?1,?col,?n,?m,?grid.clone(),?&mut?queue);
????????????add(row?+?1,?col,?n,?m,?grid.clone(),?&mut?queue);
????????????add(row,?col?-?1,?n,?m,?grid.clone(),?&mut?queue);
????????????add(row,?col?+?1,?n,?m,?grid.clone(),?&mut?queue);
????????????L?+=?1;
????????}
????????distance?+=?1;
????}

????if?FIND?==?0?{
????????return?-1;
????}?else?{
????????return?distance;
????}
}

unsafe?fn?add(
????i:?i32,
????j:?i32,
????n:?usize,
????m:?usize,
????grid:?Vec<Vec<i32>>,
????queue:?&mut?[[i32;?2];?10000],
)?{
????if?i?>=?0
????????&&?i?<?n?as?i32
????????&&?j?>=?0
????????&&?j?<?m?as?i32
????????&&?grid[i?as?usize][j?as?usize]?==?0
????????&&?!VISITED[i?as?usize][j?as?usize]
????{
????????FIND?+=?1;
????????VISITED[i?as?usize][j?as?usize]?=?true;
????????queue[R][0]?=?i;
????????queue[R][1]?=?j;
????????R?+=?1;
????}
}


c語(yǔ)言完整代碼如下：

#include?<stdio.h>
#include?<stdlib.h>
#include?<stdbool.h>

#define?MAX_SIZE?10000

int?queue[MAX_SIZE][2];
int?l;
int?r;
bool?visited[100][100];
int?find;

void?add(int?i,?int?j,?int?n,?int?m,?int**?grid);

int?maxDistance(int**?grid,?int?gridSize,?int*?gridColSize)?{
????l?=?0;
????r?=?0;
????find?=?0;
????int?n?=?gridSize;
????int?m?=?*gridColSize;

????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????visited[i][j]?=?false;
????????}
????}

????int?seas?=?0;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(grid[i][j]?==?1)?{
????????????????visited[i][j]?=?true;
????????????????queue[r][0]?=?i;
????????????????queue[r++][1]?=?j;
????????????}
????????????else?{
????????????????seas++;
????????????}
????????}
????}

????int?distance?=?0;
????while?(l?<?r?&&?find?<?seas)?{
????????int?size?=?r?-?l;
????????for?(int?i?=?0;?i?<?size?&&?find?<?seas;?i++,?l++)?{
????????????int?row?=?queue[l][0];
????????????int?col?=?queue[l][1];
????????????add(row?-?1,?col,?n,?m,?grid);
????????????add(row?+?1,?col,?n,?m,?grid);
????????????add(row,?col?-?1,?n,?m,?grid);
????????????add(row,?col?+?1,?n,?m,?grid);
????????}
????????distance++;
????}

????return?find?==?0???-1?:?distance;
}

void?add(int?i,?int?j,?int?n,?int?m,?int**?grid)?{
????if?(i?>=?0?&&?i?<?n?&&?j?>=?0?&&?j?<?m?&&?grid[i][j]?==?0?&&?!visited[i][j])?{
????????find++;
????????visited[i][j]?=?true;
????????queue[r][0]?=?i;
????????queue[r++][1]?=?j;
????}
}

int?main()?{
????int?gridSize?=?3;
????int?gridColSize[3]?=?{?3,?3,?3?};
????int**?grid?=?(int**)malloc(gridSize?*?sizeof(int*));
????for?(int?i?=?0;?i?<?gridSize;?i++)?{
????????grid[i]?=?(int*)malloc(gridColSize[i]?*?sizeof(int));
????}
????grid[0][0]?=?1;
????grid[0][1]?=?0;
????grid[0][2]?=?1;
????grid[1][0]?=?0;
????grid[1][1]?=?0;
????grid[1][2]?=?0;
????grid[2][0]?=?1;
????grid[2][1]?=?0;
????grid[2][2]?=?1;

????int?result?=?maxDistance(grid,?gridSize,?gridColSize);
????printf("%d\n",?result);

????grid[0][0]?=?1;
????grid[0][1]?=?0;
????grid[0][2]?=?0;
????grid[1][0]?=?0;
????grid[1][1]?=?0;
????grid[1][2]?=?0;
????grid[2][0]?=?0;
????grid[2][1]?=?0;
????grid[2][2]?=?0;

????result?=?maxDistance(grid,?gridSize,?gridColSize);
????printf("%d\n",?result);

????for?(int?i?=?0;?i?<?gridSize;?i++)?{
????????free(grid[i]);
????}
????free(grid);

????return?0;
}


c++語(yǔ)言完整代碼如下：

#include?<iostream>
#include?<vector>
#include?<cstring>

using?namespace?std;

int?queue[10000][2];
int?l;
int?r;
bool?visited[100][100];
int?find0;

int?maxDistance(vector<vector<int>>&?grid)?{
????//?清空變量
????//?只要l?=?0，r?=?0，隊(duì)列就算被清空了
????l?=?0;
????r?=?0;
????find0?=?0;
????int?n?=?grid.size();
????int?m?=?grid[0].size();
????//?清空visited
????memset(visited,?false,?sizeof(visited));
????//?大體思路?:
????//?1)?先把所有的陸地加入隊(duì)列，并且統(tǒng)計(jì)一共有多少海洋
????int?seas?=?0;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(grid[i][j]?==?1)?{
????????????????visited[i][j]?=?true;
????????????????queue[r][0]?=?i;
????????????????queue[r++][1]?=?j;
????????????}
????????????else?{
????????????????seas++;
????????????}
????????}
????}
????//?2)?從陸地開(kāi)始廣播出去(bfs)，每一塊陸地的上、下、左、右所能找到的海洋都是第一層海洋
????//?3)?第一層海洋繼續(xù)bfs，每一塊海洋的上、下、左、右所能找到的海洋都是第二層海洋
????//?4)?第二層海洋繼續(xù)bfs，每一塊海洋的上、下、左、右所能找到的海洋都是第三層海洋
????//?...
????//?也就是說(shuō)，以陸地做起點(diǎn)，每一層bfs都只找海洋！
????//?看看最深能找到多少層海洋
????int?distance?=?0;?//?這個(gè)變量就是最深的海洋層數(shù)
????while?(l?<?r?&&?find0?<?seas)?{?//?find?<?seas說(shuō)明所有的海洋塊沒(méi)有找全，繼續(xù)找！
????????int?size?=?r?-?l;
????????for?(int?i?=?0;?i?<?size?&&?find0?<?seas;?i++,?l++)?{
????????????int?row?=?queue[l][0];
????????????int?col?=?queue[l][1];
????????????if?(row?-?1?>=?0?&&?row?-?1?<?n?&&?col?>=?0?&&?col?<?m?&&?grid[row?-?1][col]?==?0?&&?!visited[row?-?1][col])?{
????????????????find0++;
????????????????visited[row?-?1][col]?=?true;
????????????????queue[r][0]?=?row?-?1;
????????????????queue[r++][1]?=?col;
????????????}
????????????if?(row?+?1?>=?0?&&?row?+?1?<?n?&&?col?>=?0?&&?col?<?m?&&?grid[row?+?1][col]?==?0?&&?!visited[row?+?1][col])?{
????????????????find0++;
????????????????visited[row?+?1][col]?=?true;
????????????????queue[r][0]?=?row?+?1;
????????????????queue[r++][1]?=?col;
????????????}
????????????if?(row?>=?0?&&?row?<?n?&&?col?-?1?>=?0?&&?col?-?1?<?m?&&?grid[row][col?-?1]?==?0?&&?!visited[row][col?-?1])?{
????????????????find0++;
????????????????visited[row][col?-?1]?=?true;
????????????????queue[r][0]?=?row;
????????????????queue[r++][1]?=?col?-?1;
????????????}
????????????if?(row?>=?0?&&?row?<?n?&&?col?+?1?>=?0?&&?col?+?1?<?m?&&?grid[row][col?+?1]?==?0?&&?!visited[row][col?+?1])?{
????????????????find0++;
????????????????visited[row][col?+?1]?=?true;
????????????????queue[r][0]?=?row;
????????????????queue[r++][1]?=?col?+?1;
????????????}
????????}
????????distance++;
????}
????return?find0?==?0???-1?:?distance;
}

int?main()?{
????vector<vector<int>>?grid?=?{?{1,0,1},?{0,0,0},?{1,0,1}?};
????cout?<<?maxDistance(grid)?<<?endl;?
????grid?=?{?{1,0,0},?{0,0,0},?{0,0,0}?};
????cout?<<?maxDistance(grid)?<<?endl;
}