腐烂的苹果

#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;
    }
};

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
}

//每一个腐烂苹果，过了一分钟，都会影响上下左右（即下一个层次）苹果的状态，依次类推直到下一层次没有好苹果可以影响到（没有好苹果了，或者影响不到），明显的广度优先搜索
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;
        }

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
**/

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;
};

# -*- 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