[leetcode #994 Rotting Oranges]

Problem

You are given an m x n grid where each cell can have one of three values:

・ 0 representing an empty cell,
・ 1 representing a fresh orange, or
・ 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent 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.
Example 1:

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

Example 2:

Input: grid = [[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: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

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

Idea

この問題の前提は、腐ったオレンジがそばにあると、新鮮なオレンジが1分後に腐ったオレンジになることです.Gridの上のすべてのオレンジが腐ったオレンジになるまで少なくとも数分かかります.
毎回Grid全体を探索する方法がありますが、このように解くと時間制限Exceededが出てくるので、リストを使うことにしました.最初はGrid全体で検索し、腐ったオレンジをリストに入れ、新鮮なオレンジをオレンジ数に数えます.新鮮なオレンジの数を数える理由は、腐ったオレンジになる可能性を適用した後、新鮮なオレンジが残っているかどうかを確認するためです.
時間を測るために腐ったオレンジになり、警戒値をリストに入れた.リストの要素が境界値であり、残りの要素がなければ、腐ったオレンジ色を生成することはできません.リストに残っている元素があれば、すぐに腐るオレンジがあることを意味しますので、時間を1分延長し、腐るオレンジが現れることを確認します.
リストから取り出した腐ったオレンジのインデックスを利用して、周囲の新鮮なオレンジを腐ったオレンジに変えます.交換したオレンジはリストに入れられ、新鮮なオレンジの数は1つ減ります.これにより,境界値が1人残るまでGrid全体を調べることができる.
新鮮なオレンジがまだある場合だけ、-1に戻る必要があります.そうしないと、必要な時間は1に戻ることができます.

Solution

class Solution {
    public int orangesRotting(int[][] grid) {
        int rowLen = grid.length;
        int colLen = grid[0].length;

        List<int[]> list = new ArrayList<>();
        int cnt = 0;
        for (int i=0; i < rowLen; i++) {
            for (int j=0; j < colLen; j++) {
                if (grid[i][j] == 1)
                    cnt++;
                else if (grid[i][j] == 2)
                    list.add(new int[]{i, j});
            }
        }

        list.add(new int[]{-1, -1});

        int minMinutes = 0;
        while (!list.isEmpty()) {
            int[] rotten = list.remove(0);
            int rottenRow = rotten[0];
            int rottenCol = rotten[1];
            if (rottenRow == -1 && rottenCol == -1) {
                if (list.size() == 0)
                    break;
                list.add(new int[]{-1, -1});
                minMinutes++;
                continue;
            }

            if (rottenRow != 0 && grid[rottenRow-1][rottenCol] == 1) {
                grid[rottenRow-1][rottenCol] = 2;
                list.add(new int[]{rottenRow-1, rottenCol});
                cnt--;
            }
            if (rottenRow != rowLen-1 && grid[rottenRow+1][rottenCol] == 1) {
                grid[rottenRow+1][rottenCol] = 2;
                list.add(new int[]{rottenRow+1, rottenCol});
                cnt--;
            }
            if (rottenCol != 0 && grid[rottenRow][rottenCol-1] == 1) {
                grid[rottenRow][rottenCol-1] = 2;
                list.add(new int[]{rottenRow, rottenCol-1});
                cnt--;
            }
            if (rottenCol != colLen-1 && grid[rottenRow][rottenCol+1] == 1) {
                grid[rottenRow][rottenCol+1] = 2;
                list.add(new int[]{rottenRow, rottenCol+1});
                cnt--;
            }
        }

        return cnt != 0 ? -1 : minMinutes;
    }
}

とても良い結果が出ました!

Reference

https://leetcode.com/problems/rotting-oranges/