首页 > 试题广场 >

腐烂的苹果

[编程题]腐烂的苹果

热度指数：1509 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 $n \times m \$ 的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。

其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。

腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1

数据范围： $1 \le n , m \le 1000 \$ ，网格中的值满足 $0 \le val \le 2 \$

示例1

输入

[[2,1,1],[1,0,1],[1,1,1]]

输出

示例2

输入

[[2,1,0],[1,0,1],[0,0,0]]

输出

-1

算法知识视频讲解

唐氏综合征

1. 记录好的和坏的苹果

2.依次遍历坏的苹果周围四个方向，如果是好苹果，则将其置为坏苹果，继续加入队列遍历

3. 直到队列为null 则遍历结束，如果仍然有好的苹果剩余，则说明被空格子包围.

  public int rotApple(ArrayList<ArrayList<Integer>> grid) {
            int n = grid.size();
            int m = grid.get(0).size();
            int freshApples = 0;
            
            // 记录下腐烂的苹果
            Deque<int[]> queue = new LinkedList<>();

            // 遍历网格,记录腐烂的苹果和完好的苹果
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid.get(i).get(j) == 2) {
                        queue.offer(new int[]{i, j});
                    } else if (grid.get(i).get(j) == 1) {
                        freshApples++;
                    }
                }
            }

            int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
            int minutes = 0;

            // BFS遍历
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] cell = queue.poll();
                    assert cell != null;
                    int row = cell[0], col = cell[1];

                    // 检查四个相邻位置
                    for (int[] dir : directions) {
                        int newRow = row + dir[0], newCol = col + dir[1];
                        if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && grid.get(newRow).get(newCol) == 1) {
                            grid.get(newRow).set(newCol, 2);
                            freshApples--;
                            // 将腐烂的苹果加入队列继续寻找
                            queue.offer(new int[]{newRow, newCol});
                        }
                    }
                }
                minutes++; // 经过一分钟
            }

            return freshApples == 0 ? minutes - 1 : -1; // 如果还有完好的苹果,返回-1,否则返回分钟数
        }

发表于 2024-05-06 21:42:50 回复(0)

bitsun

#include <utility>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */
    int rotApple(vector<vector<int>>& vv)
    {
        // write code here

        //2下标，第几分钟的腐烂苹果
        //map<int,int> mp;
        //进队列
        queue<pair<pair<int, int>, int>> qm;

        int row = vv.size(), col = vv[0].size();
        //初始化腐烂苹果
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (vv[i][j] == 2) qm.emplace(make_pair(i, j), 0);
            }
        }

        int minute = 0;

        while (!qm.empty())
        {
            pair<pair<int, int>, int> mp = qm.front();
            qm.pop();

            int i = mp.first.first;
            int j = mp.first.second;
            minute = mp.second;

            if (caculate(i + 1, j, vv)) qm.emplace(make_pair(i + 1, j), minute + 1);
            if (caculate(i - 1, j, vv)) qm.emplace(make_pair(i - 1, j), minute + 1);
            if (caculate(i, j + 1, vv)) qm.emplace(make_pair(i, j + 1), minute + 1);
            if (caculate(i, j - 1, vv)) qm.emplace(make_pair(i, j - 1), minute + 1);
        }

        int flag = 0;
        for (auto& e : vv)
        {
            for (auto& ee : e)
            {
                if (ee == 1)
                    flag = 1;
            }
        }

        return flag == 1 ? -1 : minute;
    }

    bool caculate(int i, int j, vector<vector<int>>& vv)
    {
        if (i < 0 || j < 0 || i >= vv.size() || j >= vv[0].size()) return false;

        if (vv[i][j] == 1)
        {
            vv[i][j] = 2;
            return true;
        }
        else
            return false;
    }
};

编辑于 2024-04-19 11:13:42 回复(0)

小谷围做题家

package main

import "strconv"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @return int整型
*/
func rotApple( grid [][]int ) int {
    n,m:=len(grid),len(grid[0])
    vis:=map[string]bool{}
    q:=[][]int{}
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if grid[i][j]==2{
                q=append(q,[]int{i,j})
            }
            if grid[i][j]==1{
                k:=strconv.Itoa(i)+"-"+strconv.Itoa(j)
                vis[k]=true
            }
        }
    }
    dirs:=[][]int{[]int{1,0},[]int{-1,0},[]int{0,1},[]int{0,-1}}
    cnt:=0
    for len(q)>0{
        new_q:=[][]int{}
        for _,qi:=range q{
            for _,dir:=range dirs{
                x,y:=qi[0]+dir[0],qi[1]+dir[1]
                if x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1{
                    grid[x][y]=2
                    k:=strconv.Itoa(x)+"-"+strconv.Itoa(y)
                    delete(vis,k)
                    new_q=append(new_q,[]int{x,y})
                }
            }
        }
        if len(new_q)>0{
            cnt++
        }
        q=new_q
    }
    if len(vis)>0{
        return -1
    }
    return cnt
}

发表于 2023-03-16 00:06:26 回复(0)

C++

牛客541678616号

无难度，相比于原本的BFS算法，只是开局多push几个距离为0的点（烂苹果）

#include <queue>
class Solution {
public:

    int xx[4]={1,-1,0,0};
    int yy[4]={0,0,1,-1};
    int bfs[1010][1010];
    int rotApple(vector<vector<int> >& grid) {
        queue<pair<int,int>>que;
        int good=0;
        memset(bfs,-1,sizeof bfs);
        int xLen=grid.size(),yLen=grid[0].size();
        for(int i=0;i<xLen;i++)
            for(int s=0;s<yLen;s++)
            {
                if(grid[i][s]==1)
                    good++;
                else if(grid[i][s]==2)
                {
                    bfs[i][s]=0;
                    que.push({i,s});
                } 
            }
        
        while(!que.empty())
        {
            int x=que.front().first,y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++)
            {
                int X=xx[i]+x,Y=yy[i]+y;
                if(X<0||X>=xLen||Y<0||Y>=yLen)//超出
                    continue;
                if(grid[X][Y]==0)continue;//阻挡
                if(bfs[X][Y]!=-1)continue;//走过
                bfs[X][Y]=bfs[x][y]+1;
                que.push({X,Y});
                if(grid[X][Y]==1)
                {
                    good--;
                    grid[X][Y]=2;
                    if(good==0)
                        return bfs[X][Y]; 
                }
            }
        }
        return -1;
    }
};

发表于 2023-03-05 21:45:30 回复(0)

Java

牛客585981974号

//每一个腐烂苹果，过了一分钟，都会影响上下左右（即下一个层次）苹果的状态，依次类推直到下一层次没有好苹果可以影响到（没有好苹果了，或者影响不到），明显的广度优先搜索
public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        //对应上下左右坐标的改变
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int m = grid.size(), n = grid.get(0).size();
        Queue<int[]> que = new LinkedList<>();
        int count = 0;
        //遍历，腐烂苹果的坐标放入队列，用于改变上下左右坐标处苹果的状态，count记录好苹果的数量，
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 2) {
                    que.add(new int[] {i, j});
                } else if (grid.get(i).get(j) == 1) {
                    count++;
                }
            }
        }
        int round = 0;
        while (count > 0 && !que.isEmpty()) {
            //过去了多少分钟
            round++;
            //队列长度会变，直接把que.size()放入for循环会出错
            int size = que.size();
            for (int i = 0; i < size; i++) {
                int[] org = que.poll();
                //改变当前腐烂苹果的上下左右处苹果的状态
                for (int j = 0; j < 4; j++) {
                    int x = org[0] + dx[j];
                    int y = org[1] + dy[j];
                    //边界判定
                    if (x >= 0 && y >= 0 && x < m && y < n && grid.get(x).get(y) == 1) {
                        grid.get(x).set(y,2);
                        que.add(new int[] {x, y});
                        count--;
                    }
                }
            }
        }
        if (count != 0) {
            return -1;
        } else {
            return round;
        }

发表于 2023-02-15 11:55:02 回复(0)

Java

skwan

import java.util.*;


public class Solution {
    private static int[][] dirs = new int[][] {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };
    
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {  
        int n = grid.size(), m = grid.get(0).size();
        // que: 存放当前时刻已经腐烂的苹果
        Deque<int[]> que = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++){
                if (grid.get(i).get(j) == 2) {
                    que.add(new int[]{i, j});
                }
            }
        }
        int ans = 0;
        while(!que.isEmpty()) {
            ans++;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                int[] cur = que.pollFirst();
                int x = cur[0], y = cur[1];
                for (int[] dir : dirs) {
                    int x0 = x + dir[0];
                    int y0 = y + dir[1];
                    if (x0 >= 0 && x0 < n && y0 >= 0 && y0 < m 
                        && grid.get(x0).get(y0) == 1) {
                        grid.get(x0).set(y0, 2);
                        que.add(new int[]{x0, y0});
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid.get(i).get(j) == 1) {
                    return -1;
                }
            } 
        }
        // 除去初始时刻
        return ans - 1;
    }
}

/**
2 1 1
1 0 1
1 1 1
**/

发表于 2022-07-18 08:50:59 回复(0)

C++

牛客487629784号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int rotApple(vector<vector<int> >& grid) {
        // write code here
        //用递归则是深度优先搜索，用队列则是广度优先搜索
        queue<int> bad;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(grid[i][j]==2)
                {
                    bad.push(i);
                    bad.push(j);
                    grid[i][j]=-1;//标记
                }
            }
        }
        help(grid,bad);
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(grid[i][j]==1)
                {
                    return -1;
                }
            }
        }
        return maxx;
    }
    void help(vector<vector<int> >& grid,queue<int> qe)
    {
        int cnt=-1;
        while(!qe.empty())
        {
            cnt++;
            int size=qe.size()/2;

            for(int i=0;i<size;i++)
            {
                int curx=qe.front();
                qe.pop();
                int cury=qe.front();
                qe.pop();

                if((curx-1>=0)&&(grid[curx-1][cury]>0))
                {
                    qe.push(curx-1);
                    qe.push(cury);
                    grid[curx-1][cury]=-1;//访问标记,push后立刻给访问标记，防止相同苹果多次入队
                }
                if((curx+1<grid.size())&&(grid[curx+1][cury]>0))
                {
                    qe.push(curx+1);
                    qe.push(cury);
                    grid[curx+1][cury]=-1;//访问标记
                }
                if((cury-1>=0)&&(grid[curx][cury-1]>0))
                {
                    qe.push(curx);
                    qe.push(cury-1);
                    grid[curx][cury-1]=-1;//访问标记
                }
                if((cury+1<grid[0].size())&&(grid[curx][cury+1]>0))
                {
                    qe.push(curx);
                    qe.push(cury+1);
                    grid[curx][cury+1]=-1;//访问标记
                }
            }
        }
        maxx=max(maxx,cnt);
    }
private:
    int maxx=-1;
};

发表于 2022-07-01 16:23:36 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param grid int整型二维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/54ab9865ce7a45968b126d6968a77f34?tpId=196&tqId=40529&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        典型的广搜
        初始化：
            将所有grid[i][j] == 2的坐标加入队列queue， count = 0
        当queue不空时，进行如下处理：
            count += 1
            遍历queue，向上下左右四个方向，有完整的苹果的位置进行扩展，标记扩展几点为grid[i][j]=2，记录扩展坐标至newQueue
            遍历结束，将newQueue赋值给queue
        返回值：count
    复杂度：
        时间复杂度：O(mn)
        空间复杂度：O(mn)
    """

    def rotApple(self, grid):
        # write code here
        m, n = len(grid), len(grid[0])

        queue, hashMap = [], set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:  # 初始，记录所有腐烂苹果的坐标
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    hashMap.add((i, j))

        count, directions = -1, [(0, 1), (1, 0), (0, -1), (-1, 0)]
        while queue:
            newQueue = []
            count += 1
            for x, y in queue:
                for i, j in directions:
                    tx, ty = x + i, y + j
                    if tx < 0&nbs***bsp;tx >= m&nbs***bsp;ty < 0&nbs***bsp;ty >= n&nbs***bsp;grid[tx][ty] != 1:
                        continue
                    grid[tx][ty] = 2
                    hashMap.remove((tx, ty))
                    newQueue.append((tx, ty))
            queue = newQueue
        return count if not hashMap else -1


if __name__ == "__main__":
    sol = Solution()

    matrix = [[2, 1, 1], [1, 0, 1], [1, 1, 1]]

    # matrix = [[2, 1, 0], [1, 0, 1], [0, 0, 0]]

    res = sol.rotApple(matrix)

    print res

发表于 2022-06-26 21:47:37 回复(0)