1. 題目

顏色填充。編寫函數(shù)，實(shí)現(xiàn)許多圖片編輯軟件都支持的“顏色填充”功能。

給定一個屏幕（以二維數(shù)組表示，元素為顏色值）、一個點(diǎn)和一個新的顏色值，將新顏色值填入這個點(diǎn)的周圍區(qū)域，直到原來的顏色值全都改變。

示例1:輸入： image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2輸出：[[2,2,2],[2,2,0],[2,0,1]]解釋: 在圖像的正中間，(坐標(biāo)(sr,sc)=(1,1)), 在路徑上所有符合條件的像素點(diǎn)的顏色都被更改成2。 注意，右下角的像素沒有更改為2， 因?yàn)樗皇窃谏舷伦笥宜膫€方向上與初始點(diǎn)相連的像素點(diǎn)。說明： image 和 image[0] 的長度在范圍 [1, 50] 內(nèi)。 給出的初始點(diǎn)將滿足 0 <= sr < image.length 和 0 <= sc < image[0].length。 image[i][j] 和 newColor 表示的顏色值在范圍 [0, 65535]內(nèi)。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/color-fill-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 標(biāo)準(zhǔn)的廣度和深度優(yōu)先搜索，模板題

2.1 BFS

class Solution { public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {int m = image.size(), n = image[0].size();int original = image[sr][sc], k, x, y, x0, y0;vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};queue<vector<int>> q;vector<vector<bool>> visited(m, vector<bool>(n,false));q.push({sr,sc});visited[sr][sc] = true;image[sr][sc] = newColor;while(!q.empty()){x0 = q.front()[0];y0 = q.front()[1];q.pop();for(k = 0; k < 4; ++k){x = x0+dir[k][0];y = y0+dir[k][1];if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && image[x][y]==original){q.push({x,y});visited[x][y] = true;image[x][y] = newColor;}}}return image;} };

2.2 DFS

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};int m, n, original;vector<vector<bool>> visited; public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {m = image.size(), n = image[0].size();original = image[sr][sc];visited.resize(m, vector<bool>(n,false));visited[sr][sc] = true;image[sr][sc] = newColor;dfs(image,sr,sc,newColor);return image;}void dfs(vector<vector<int>>& image, int x0, int y0, int newColor){int x, y;for(int k = 0; k < 4; ++k){x = x0+dir[k][0];y = y0+dir[k][1];if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && image[x][y]==original){visited[x][y] = true;image[x][y] = newColor;dfs(image,x,y,newColor);//占領(lǐng)即可，不必回溯}}} };

總結(jié)

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 08.10. 颜色填充（BFS/DFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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