烂橘子 LeetCode

Question

我正在尝试解决这个问题：https://leetcode.com/problems/rotting-oranges/

link 比我用视觉效果解释得更好，但基本上你必须让“烂”橙子（值 2）旁边的每个橙子也烂掉。

我正在使用 BFS 来解决这个问题。我首先为所有烂橙子制作一个队列，然后将其传递给我的 bfs 函数，该函数检查是否可以进行 (up/down/left/right)，如果可以，则将其添加到队列中并更改值以显示节点已经被访问过。

我的解决方案没有给出正确答案，我不确定逻辑失误在哪里。

class Solution {
    public int orangesRotting(int[][] grid) {
        
        //get all 2's into a queue
        //iterate over 2 making all oranges rotten
        //iterate grid again --> anything that's not 2, return -1
        //else return count
        Queue<String> q = new LinkedList<>();
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 2) {
                    q.add("" + i + j);
                }
            }
        }

        int count = getMinutes(grid, q);
        
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return count;
    }
    
    public static int getMinutes(int[][] grid, Queue<String> q) {
        
        Queue<String> rotten = new LinkedList<>();

        int count = 0;
        final int[][] SHIFTS = {
            {1,0},
            {-1,0},
            {0,1},
            {0,-1}
        };
        
        while(true) {
            while(!q.isEmpty()) {
                String s = q.remove();
                 int i = Integer.parseInt(s.substring(0, s.length() - 1));
                 int j = Integer.parseInt(s.substring(s.length() - 1));
                
                for(int[] points : SHIFTS) {
                    int tempI = i + points[0];
                    int tempJ = j + points[1];
                    if(isValidMove(grid, tempI, tempJ)) {
                        rotten.add("" + tempI + tempJ);
                        grid[tempI][tempJ] =  2; //it's visited
                    }
                }
            }
            if(rotten.isEmpty()) {
                return count;
            }
            count++;
            q = rotten;
        }
    }
    
    public static boolean isValidMove(int[][] grid, int i, int j) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != 1) {
            return false;
        }
        return true;
    }
}

Answer 1

我建议你不要这样做：q.add("" + i + j);你如何区分{11,2}和{1, 12}，两者给出相同的字符串"112"？只需使用 q.add( new int[]{i, j} ) 它不应该导致太多的性能问题，它们只是整数。事实上恰恰相反。应该会更快。
现在进入主要问题，除了您需要在 while ( true ) 中初始化一个新队列之外，您的算法几乎是正确的，因为您必须每次都从一个新队列开始刷新当前队列的时间。这个想法是你从一排已经腐烂的橙子开始。腐烂相邻的橘子，并建立一个由新腐烂的橘子组成的新队列。然后重复，直到新烂橙子的新队列为空。所以每次你从已经腐烂的橙子开始时，它都必须是一个新的队列。

修改后的 getMinutes 更正了主要问题：

   public static int getMinutes(int[][] grid, Queue<String> q) {
        
        int count = 0;
        final int[][] SHIFTS = {
            {1,0},
            {-1,0},
            {0,1},
            {0,-1}
        };
        
        while(true) {
            Queue<String> rotten = new LinkedList<>();
            while(!q.isEmpty()) {
                String s = q.remove();
                 int i = Integer.parseInt(s.substring(0, s.length() - 1));
                 int j = Integer.parseInt(s.substring(s.length() - 1));
                
                for(int[] points : SHIFTS) {
                    int tempI = i + points[0];
                    int tempJ = j + points[1];
                    if(isValidMove(grid, tempI, tempJ)) {
                        rotten.add("" + tempI + tempJ);
                        grid[tempI][tempJ] =  2; //it's visited
                    }
                }
            }
            if(rotten.isEmpty()) {
                return count;
            }
            count++;
            q = rotten;
        }
    }

Answer 2

看起来不错！

我的猜测是您的解决方案缺失 return 0 因为如果没有 freshOranges 早。
这类似于一种广度优先搜索算法，尽管出于懒惰目的（^_^）而被塞进一个函数中：

public class Solution {

    private static final int[][] directions = new int[][] {
        {1, 0},
        { -1, 0},
        {0, 1},
        {0, -1}
    };

    public static final int orangesRotting(
        int[][] grid
    ) {
        final int rows = grid.length;
        final int cols = rows > 0 ? grid[0].length : 0;

        if (rows == 0 || cols == 0) {
            return 0;
        }

        Queue<int[]> queue = new LinkedList<>();
        int freshOranges = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == 2) {
                    queue.offer(new int[] {row, col});

                } else if (grid[row][col] == 1) {
                    freshOranges++;
                }
            }
        }

        if (freshOranges == 0) {
            return 0;
        }

        int count = 0;

        while (!queue.isEmpty()) {
            count++;
            final int size = queue.size();

            for (int i = 0; i < size; i++) {
                final int[] cell = queue.poll();

                for (int[] direction : directions) {
                    final int row = cell[0] + direction[0];
                    final int col = cell[1] + direction[1];

                    if (
                        row < 0 ||
                        col < 0 ||
                        row >= rows ||
                        col >= cols ||
                        grid[row][col] == 0 ||
                        grid[row][col] == 2
                    ) {
                        continue;
                    }

                    grid[row][col] = 2;
                    queue.offer(new int[] {row, col});
                    freshOranges--;
                }
            }
        }

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

烂橘子 LeetCode

Rotten Oranges LeetCode

java

algorithm

graph

breadth-first-search

看起来不错！