Rotting Oranges (M)

題目

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

題意

給定一個矩陣包含若干個新鮮橘子和爛橘子，每一分鐘每個爛橘子相鄰四個橘子都會腐爛，問經過幾分鐘只剩下爛橘子，

思路

先遍歷一遍矩陣，將所有爛橘子的位置加入佇列，并統計新鮮橘子的個數，每一分鐘的程序相當于將當前佇列中位置全部出堆疊，判斷相鄰4個位置是否有新鮮橘子，有則將其變為爛橘子并將其位置加入佇列以便下一分鐘的處理，最后判斷還有沒有新鮮橘子，

代碼實作

Java

class Solution {
    public int orangesRotting(int[][] grid) {
        int count = 0;
        int minutes = 0;
        int[] xPlus = { 0, 1, 0, -1 };
        int[] yPlus = { 1, 0, -1, 0 };
        int m = grid.length, n = grid[0].length;
        Queue<Coor> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.offer(new Coor(i, j));
                } else if (grid[i][j] == 1) {
                    count++;
                }
            }
        }

        while (!q.isEmpty()) {
            int size = q.size();

            for (int j = 0; j < size; j++) {
                Coor cur = q.poll();
                for (int i = 0; i < 4; i++) {
                    int nextX = cur.x + xPlus[i];
                    int nextY = cur.y + yPlus[i];
                    if (isValid(m, n, nextX, nextY) && grid[nextX][nextY] == 1) {
                        grid[nextX][nextY] = 2;
                        count--;
                        q.offer(new Coor(nextX, nextY));
                    }
                }
            }

            if (!q.isEmpty()) minutes++;
        }

        return count == 0 ? minutes : -1;
    }

    private boolean isValid(int m, int n, int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}

class Coor {
    int x;
    int y;

    public Coor(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5285.html

標籤：其他

上一篇：LeetCode----K 個一組翻轉鏈表

下一篇：leetcode刷題筆記-1. 兩數之和（java實作）

0994. Rotting Oranges (M)

Rotting Oranges (M)

題目

題意

思路

代碼實作

Java