Skip to content

leetcode 1034. 边框着色

我的解题

我是按照 labuladong Flood Fill 算法详解 中,给出的解题思路写的。

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> colorBorder(vector<vector<int>> &grid, int r0, int c0, int color)
    {
        vector<vector<bool>> visited { grid.size() };
        for (auto &&v : visited)
        {
            v = vector<bool>(grid[0].size(), false);
        }
        int oldColor = grid[r0][c0]; // 旧颜色
        fill(grid, r0, c0, oldColor, color, visited);
        return grid;
    }
    /**
     * @brief
     *
     * @param image
     * @param x
     * @param y
     * @param newColor
     */
    int fill(vector<vector<int>> &image, int x, int y, int oldColor, int newColor, vector<vector<bool>> &visited)
    {
        if (!inArea(image, x, y))
            return 0;
        if (visited[x][y]) // 必须要先判断`visited[x][y]`,然后判断`image[x][y] != oldColor`
            return 1;
        if (image[x][y] != oldColor)
            return 0;

        visited[x][y] = true;
        int surround = fill(image, x - 1, y, oldColor, newColor, visited) + fill(image, x + 1, y, oldColor, newColor, visited) + fill(image, x, y - 1, oldColor, newColor, visited) + fill(image, x, y + 1, oldColor, newColor, visited);
        if (surround < 4)
        {
            image[x][y] = newColor;
        }
        return 1;
    }
    bool inArea(vector<vector<int>> &image, int x, int y)
    {
        return (x >= 0 && x < image.size()) && (y >= 0 && y < image[0].size());
    }
};
int main()
{
    vector<vector<int>> image { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } };
    Solution s;
    s.colorBorder(image, 1, 1, 2);

}
// g++ test.cpp --std=c++11 -pedantic -Wall -Wextra