【错题集-编程题】腐烂的苹果（多源 BFS + 最短路）

题目链接：腐烂的苹果_牛客题霸_牛客网 (nowcoder.com)

一、分析题目

多源 BFS 问题，加一点最短路的思想，固定套路。

二、代码

//看了题解之后AC的代码
class Solution {
private:
    int n, m;
    bool vis[1010][1010];
    int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int rotApple(vector<vector<int> >& grid) {
        n=grid.size(), m=grid[0].size();
        queue<pair<int, int>> q;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(grid[i][j]==2)
                    q.push({i, j});
        int t=0;
        while(q.size())
        {
            t++;
            int size=q.size();
            while(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<n && y>=0 && y<m && !vis[x][y] && grid[x][y]==1)
                    {
                        vis[x][y]=true;
                        q.push({x, y});
                    }
                }
            }
        }
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(!vis[i][j] && grid[i][j]==1)
                    return -1;
        return t-1;
    }
};

//值得学习的代码
class Solution
{
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[1010][1010] = { 0 };

public:
    int rotApple(vector<vector<int> >& grid) 
    {
        m = grid.size(), n = grid[0].size();

        queue<pair<int, int>> q;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(grid[i][j] == 2)
                    q.push({i, j});
 
        int ret = 0;
        while(q.size())
        {
            int sz = q.size();
            ret++;
            while(sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for(int i = 0; i < 4; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
                    {
                        vis[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(grid[i][j] == 1 && !vis[i][j]) 
                    return -1; 

    return ret - 1;
    }
};

三、反思与改进

这道题目我是用 dfs 做的，暴力过了 70% 的样例，但我很清楚正确答案肯定是要用到 bfs，是层序遍历整个网格，但在做题的时候把 bfs 最基本的内容给忘记了，连其对应辅助的栈结构都没想起来。还有一个主要原因是：多源 bfs 这一块我还没有进行系统性的学习，目前只接触了最基础的 bfs，不过我不认为这是做不出这道题目的理由，究其根本是连本质都忘记了，而不是 bfs 的扩展没学习到，所以要抓紧时间把 bfs 相关算法学习完，并将其算法原理熟烂于心。