算法原理：

使用隊(duì)列進(jìn)行層序遍歷(bfs)。首先要記錄原坐標(biāo)的像素值，再以這個(gè)坐標(biāo)為中心，上下左右四個(gè)方向進(jìn)行遍歷，如果發(fā)現(xiàn)有相等的像素值，就把這個(gè)坐標(biāo)入隊(duì)列并且修改成指定的像素值。接著再取出隊(duì)頭元素，進(jìn)行判斷，修改，遍歷四個(gè)方向，入隊(duì)列…直到隊(duì)列為空，此時(shí)就把圖中所有等于原像素值的位置修改成了指定的像素值。

細(xì)節(jié)/技巧問(wèn)題：

(1) 記錄完原坐標(biāo)的像素值時(shí)，先進(jìn)行一次判斷，是否等于要修改的值，如果是，就直接返回圖像。

(2) 要得到上下左右四個(gè)方向的坐標(biāo)有技巧。

(3) 要注意遍歷四個(gè)方向時(shí)坐標(biāo)不能越界。

代碼實(shí)現(xiàn)：

class Solution 
{typedef pair<int, int> PII;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int prev = image[sr][sc];if(prev == color) return image; // 處理特殊情況int m = image.size();int n = image[0].size();queue<PII> q;q.push({sr ,sc});while(q.size()){auto [a, b] = q.front();q.pop();if(image[a][b] == prev) image[a][b] = color;// 判斷上下左右的值for(int i = 0; i < 4; i++){int x = a + dx[i];int y = b + dy[i];if(x >=0 && x < m && y >=0 && y < n && image[x][y] == prev)q.push({x, y});}}return image;}
};

算法原理：

這道題就是第一道題的進(jìn)階版，也是使用隊(duì)列層序遍歷(bfs)，只不過(guò)是多次使用bfs算法，所以把它寫成一個(gè)函數(shù)，bfs在這里的作用是標(biāo)記陸地。遍歷整個(gè)矩陣，當(dāng)遇到陸地(‘1’)并且沒(méi)有被遍歷過(guò)時(shí)，使用bfs并島嶼數(shù)量+1。

細(xì)節(jié)/技巧問(wèn)題：
(1) 當(dāng)取出隊(duì)頭坐標(biāo)進(jìn)行上下左右遍歷時(shí)，一定會(huì)遍歷到相同的位置，此時(shí)就要進(jìn)行區(qū)分。可以定義一個(gè)bool類型的標(biāo)記數(shù)組vis，如果位置已經(jīng)遍歷過(guò)，置為true，否則為false。

(2) 給bfs函數(shù)進(jìn)行傳參時(shí)，如果想要形參簡(jiǎn)潔一些，可以把一些變量定義在main函數(shù)外變?yōu)楣械?#xff0c;這樣可以減少麻煩。比如這道題里矩陣的行和列，標(biāo)記數(shù)組vis等

代碼實(shí)現(xiàn)：

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m,n;bool vis[301][301]; // 記錄位置有沒(méi)有被遍歷過(guò)，true有,false沒(méi)有
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0; //記錄島嶼數(shù)量// 遍歷整個(gè)網(wǎng)格for(int i = 0;i < m; i++){for(int j = 0;j < n; j++){// 如果是陸地并且沒(méi)有遍歷過(guò)if(grid[i][j] == '1' && !vis[i][j]){// 把這塊陸地標(biāo)記bfs( grid,i, j);ret++;}}}   return ret;}void bfs(vector<vector<char>>& grid, int i, int j){queue<pair<int ,int>> q;q.push({i, j});vis[i][j] = true; // 入隊(duì)列代表你已經(jīng)遍歷過(guò)了，要標(biāo)記while(q.size()){auto [a,b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y]){q.push({x,y});vis[x][y] = true;}}}}
};

算法原理：

這道題也是基于前兩題的bfs算法，也要多次使用bfs，所以也寫成函數(shù)。它的作用是標(biāo)記陸地并且統(tǒng)計(jì)每塊陸地的面積。遍歷矩陣，當(dāng)遇到?jīng)]有被遍歷過(guò)的陸地(1)時(shí)，調(diào)用bfs函數(shù)進(jìn)行標(biāo)記與統(tǒng)計(jì)，遇到符合要求的坐標(biāo)并且入隊(duì)列后，陸地面積+1。統(tǒng)計(jì)完每一塊陸地的面積再返回給main函數(shù)。

細(xì)節(jié)/技巧問(wèn)題：

參考前面兩題。

代碼實(shí)現(xiàn)：

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[51][51];int m,n;
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret_max = 0;int ret = 0;for(int i = 0;i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1 && !vis[i][j]){ret = bfs(grid, i, j);ret_max = max(ret, ret_max);}}}return ret_max;}int bfs(vector<vector<int>>& grid, int i, int j){int ret = 0; // 記錄島嶼面積queue<pair<int ,int>> q;q.push({i, j});vis[i][j] = true; // 記得標(biāo)記ret++;while(q.size()){auto[a,b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a+dx[k], y = b+dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]){q.push({x, y});vis[x][y] = true;ret++;}}}return ret;}
};

算法原理：

這道題也是bfs算法的綜合運(yùn)用。如果按照題意正面去解決，就是直接把除與邊界’O’(包括邊界)聯(lián)通的區(qū)域外，其余全部修改為’X’，會(huì)顯的很麻煩。所以正難則反，我們可以先把與邊界’O’(包括邊界)聯(lián)通的區(qū)域修改為其他字符，再遍歷整個(gè)數(shù)組，把剩余的’O’區(qū)域修改為’X’，最后把原來(lái)修改為的其他字符還原為’O’，這樣也可以解決問(wèn)題，并且整個(gè)代碼書寫也更清晰。當(dāng)然，這里的bfs算法也不止使用一次，所以也要寫成函數(shù)，它的作用是把與邊界’O’(包括邊界)聯(lián)通的區(qū)域修改為其他字符。

細(xì)節(jié)/技巧問(wèn)題：

參考前面三題

代碼實(shí)現(xiàn)：

class Solution 
{int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m, n;bool vis[201][201];
public:void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();// 先把邊界上的'O'區(qū)域改為無(wú)關(guān)字符for(int i = 0; i < m; i++){if(board[i][0] == 'O') bfs(board, i, 0);if(board[i][n-1] == 'O') bfs(board, i, n-1);}for(int j = 0; j < n; j++){if(board[0][j] == 'O') bfs(board, 0, j);if(board[m-1][j] == 'O') bfs(board, m-1, j);}// 再遍歷矩陣，把所有'O'改為'X'for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'O' && !vis[i][j])board[i][j] = 'X';}}// 最后還要把前面改過(guò)的'.'還原為'O'for(int i = 0; i< m; i++){for(int j = 0; j < n; j++)if(board[i][j] == '.')board[i][j] = 'O';}}void bfs(vector<vector<char>>& board, int i, int j){queue<pair<int ,int>> q;q.push({i ,j});vis[i][j] = true;board[i][j] = '.';while(q.size()){auto[a,b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a+dx[k], y = b+dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == 'O'){q.push({x, y});vis[x][y] = true;board[x][y] = '.';}}}}
};