题解 | 腐烂的苹果

class Solution 
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[1010][1010] = {0};

    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.empty())
        {
            int sz = q.size();
            ret++;
            while(sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                // 注意这是循环, 
                for(int k = 0; k < 4; k++) 
                {
                    int x = a + dx[k];
                    int y = b + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1) 
                    {
                        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;
    }
};

多源 BFS , 固定套路~~