C++ BFS相关题目

目录

图像渲染  

岛屿数量

图像渲染  

733. 图像渲染

 vis就是标记1有没有被用过

符合条件的都放到队列里，每次出队列一个，判四个，

如果要改的值与当前的值相同直接返回

注意：image[x][y] == prev要放在坐标判断的后面，不然会越界，本来想的是不成立先跳出if，不对，这个左边的判段就是为了image[x][y] == prev这个，先后顺序

class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    vectorint>> floodFill(vectorint>>& image, int sr, int sc, int color) {
        if(image[sr][sc] == color) return image;
        int m = image.size(), n = image[0].size();
        queueint, int>> q;
        q.push({sr, sc});
        int prev = image[sr][sc];
 
        while(q.size())
        {
            auto e = q.front(); q.pop();
            image[e.first][e.second] = color;
            for(int i = 0; i < 4; i++)
            {
                int x = e.first + dx[i], y = e.second + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
                    q.push({x, y});
            }
        }
        return image;
    }
};

  岛屿数量

 200. 岛屿数量

对每一个位置找联通块，对找过的1进行标记

错误：因为先是在里面定义的，发现bfs也要用，又在全局定义。。。mn不对，一直不过，第二次这样了

3.给的是string，传的是char，vs里编不过

class Solution {
public:
    vectorbool>> vis;
    vector<int> dx = {0, 0, -1, 1};
    vector<int> dy = {1, -1, 0, 0};
    int m, n;
    int numIslands(vectorchar>>& grid) {
        //加了int 导致一直不对
        m = grid.size(), n = grid[0].size();
        vis.resize(m, vector<bool>(n, false));
        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);
                }
            }
        }
        return ret;
    }
 
    void bfs(vectorchar>>& grid, int i, int j)
    {
        queueint, int>> q;
        q.push({i, j});
        vis[i][j] = true;
        while(q.size())
        {
            auto e = q.front(); q.pop();
            for(int i = 0; i < 4; i++)
            {
                int x = e.first + dx[i], y = e.second + dy[i];
                //不写范围保证，会报错
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
                {
                    q.push({x, y});
                    vis[x][y] = true;
                }
            }
        }
    }
};