Brooke

一、題目

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.

 

二、程式作法

 public class Solution
{
    public int OrangesRotting(int[][] grid)
    {
        int minutes = 0;
        int before = 0;
        int after = 0;

        int[][] rotGrid = new int[grid.Length][];
        for (int i = 0; i < grid.Length; i++)
            rotGrid[i] = new int[grid[0].Length];

        for (int i = 0; i < rotGrid.Length; i++)
            for (int j = 0; j < rotGrid[0].Length; j++)
                rotGrid[i][j] = grid[i][j];

        for (int i = 0; i < grid.Length; i++)
            for (int j = 0; j < grid[0].Length; j++)
                after += grid[i][j];

        do
        {
            before = after;
            for (int i = 0; i < rotGrid.Length; i++)
                for (int j = 0; j < rotGrid[0].Length; j++)
                    grid[i][j] = rotGrid[i][j];

            for (int i = 0; i < grid.Length; i++)
                for (int j = 0; j < grid[0].Length; j++)
                {
                    if (grid[i][j] == 1 && i > 0 && grid[i - 1][j] == 2)
                        rotGrid[i][j] = Math.Max(rotGrid[i][j], grid[i - 1][j]);
                    if (grid[i][j] == 1 && j > 0 && grid[i][j - 1] == 2)
                        rotGrid[i][j] = Math.Max(rotGrid[i][j], grid[i][j - 1]);
                }

            for (int i = grid.Length - 1; i >= 0; i--)
                for (int j = grid[0].Length - 1; j >= 0; j--)
                {
                    if (grid[i][j] == 1 && i < grid.Length - 1 && grid[i + 1][j] == 2)
                        rotGrid[i][j] = Math.Max(rotGrid[i][j], grid[i + 1][j]);
                    if (grid[i][j] == 1 && j < grid[0].Length - 1 && grid[i][j + 1] == 2)
                        rotGrid[i][j] = Math.Max(rotGrid[i][j], grid[i][j + 1]);
                }

            after = 0;
            for (int i = 0; i < rotGrid.Length; i++)
                for (int j = 0; j < rotGrid[0].Length; j++)
                    after += rotGrid[i][j];

            minutes++;
        } while (before != after);

        for (int i = 0; i < rotGrid.Length; i++)
            for (int j = 0; j < rotGrid[0].Length; j++)
                if (rotGrid[i][j] == 1)
                    return -1;

        return minutes - 1;
    }
}

 

三、思路筆記

使用動態方法 (Dynamic Programming) 處理，