文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 BFS
    • 2.2 DFS

1. 題目

給出一個二維整數網格 grid，網格中的每個值表示該位置處的網格塊的顏色。

只有當兩個網格塊的顏色相同，而且在四個方向中任意一個方向上相鄰時，它們屬于同一連通分量。

連通分量的邊界是指連通分量中的所有與不在分量中的正方形相鄰（四個方向上）的所有正方形，或者在網格的邊界上（第一行/列或最后一行/列）的所有正方形。

給出位于 (r0, c0) 的網格塊和顏色 color，使用指定顏色 color 為所給網格塊的連通分量的邊界進行著色，并返回最終的網格 grid 。

示例 1： 輸入：grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3 輸出：[[3, 3], [3, 2]]示例 2： 輸入：grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3 輸出：[[1, 3, 3], [2, 3, 3]]示例 3： 輸入：grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2 輸出：[[2, 2, 2], [2, 1, 2], [2, 2, 2]]提示： 1 <= grid.length <= 50 1 <= grid[0].length <= 50 1 <= grid[i][j] <= 1000 0 <= r0 < grid.length 0 <= c0 < grid[0].length 1 <= color <= 1000

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/coloring-a-border
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 簡單的BFS/DFS即可
• 判斷條件：周圍點出界，或 周圍的點顏色不同，就把當前點標記為邊界

2.1 BFS

class Solution { public:vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {int m = grid.size(), n = grid[0].size(), i, j, k, x, y;vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};int origin = grid[r0][c0];vector<vector<bool>> vis(m, vector<bool>(n, false));queue<pair<int,int>> q;q.push(make_pair(r0, c0));vis[r0][c0] = true;while(!q.empty()){i = q.front().first;j = q.front().second;q.pop();for(k = 0; k < 4; ++k){x = i + dir[k][0];y = j + dir[k][1];if(x >=0 && x<m && y>=0 && y<n)//在界內{if(vis[x][y]) continue;//訪問過了，下一個if(grid[x][y] != origin)//沒有訪問，顏色不同grid[i][j] = color;// i, j 旁邊的 x, y跟它不一樣，邊界else//沒有訪問，顏色一樣，正常入隊{q.push({x,y});vis[x][y] = true;}}else//出界了grid[i][j] = color;//i,j 是邊界}}return grid;} };

40 ms 13 MB

2.2 DFS

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};int m, n, origin, col; public:vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {m = grid.size(), n = grid[0].size();origin = grid[r0][c0], col = color;vector<vector<bool>> vis(m, vector<bool>(n, false));vis[r0][c0] = true;dfs(grid,r0,c0,vis);return grid;}void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& vis){int x, y, k;for(k = 0; k < 4; ++k){x = i + dir[k][0];y = j + dir[k][1];if(x >=0 && x<m && y>=0 && y<n)//在界內{if(vis[x][y]) continue;//訪問過了，下一個if(grid[x][y] != origin)//沒有訪問，顏色不同grid[i][j] = col;// i, j 旁邊的 x, y跟它不一樣，邊界else//沒有訪問，顏色一樣{vis[x][y] = true;dfs(grid, x, y, vis);}}else//出界了grid[i][j] = col;//i,j 是邊界}} };

36 ms 12.9 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1034. 边框着色（BFS/DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。