给定一个维度为 r*c 的矩阵，其中矩阵中的每个单元格都可以具有值 0、1 或 2，其含义如下： 0 ： 空单元格 1：细胞有新鲜的橙子 2 ： 细胞有腐烂的橙子
因此，我们必须确定腐烂所有橙子所需的最短时间是多少。索引 [i，j] 处的烂橙子可以在单位时间内腐烂索引 [i-1，j]、[i+1，j]、[i，j-1]、[i，j+1](上、下、左和右(处的其他新鲜橙子。如果不可能腐烂每个橙子，那么只需返回 -1。
输入： 输入的第一行包含一个整数 T，表示测试用例的数量。每个测试用例包含两个整数 r 和 c，其中 r 是行数，c 是数组 a[] 中的列数。下一行包含数组 a[].
这是我编写的代码
class GFG {
public static boolean isSafe(int[][] M, boolean[][] visited, int i, int j) {
int R = M.length;
int C = M[0].length;
return (i >= 0 && i < R && j >= 0 && j < C && (!visited[i][j]) && M[i][j] != 0);
}
public static int findMinDist(int[][] M, boolean[][] visited, int i, int j, int dist) {
if (M[i][j] == 2)
return dist;
int[] x_pos = { 1, -1, 0, 0 };
int[] y_pos = { 0, 0, -1, 1 };
visited[i][j] = true;
int min = Integer.MAX_VALUE;
for (int k = 0; k < 4; k++) {
if (isSafe(M, visited, i + x_pos[k], j + y_pos[k]))
min = Math.min(min, findMinDist(M, visited, i + x_pos[k], j + y_pos[k], dist + 1));
}
return min;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
int R = sc.nextInt();
int C = sc.nextInt();
int[][] M = new int[R][C];
boolean[][] visited = new boolean[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
M[i][j] = sc.nextInt();
}
}
int[][] time = new int[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (M[i][j] == 1)
time[i][j] = findMinDist(M, new boolean[R][C], i, j, 0);
}
}
int maxTime = Integer.MIN_VALUE;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
maxTime = Math.max(time[i][j], maxTime);
}
}
System.out.println(maxTime == Integer.MAX_VALUE ? -1 : maxTime);
}
}
}
我试图找到每个 2 的最小距离 1.
它不适用于测试用例
输入：
1
2 5
1 1 1 1 1 1 0 2 1 1 1 1
其正确输出为：
4
我的代码的输出是：
6
请建议代码有什么问题。
首先创建一个矩阵来存储橙子腐烂的时间。您可以使用-1初始化所有插槽。您将使用 BFS，但您不需要"标记"矩阵，因为橙子腐烂的时间已经足以告诉您是否访问过某个插槽。
遍历原始矩阵。当你找到一个值2，做一个BFS从那里开始腐烂新鲜的橙子。此BFS还应说明每个橙子腐烂的时间，并且您必须始终保持最短的时间。如果此刻正在看的橙子在时间t1已经腐烂，而你刚刚及时到达那里t2，t2 < t1，假装这个橙子是新鲜的，然后像这样放入 BFS 队列。
完成后，遍历时间矩阵并返回找到的最大值。
class Pair {
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
public int x;
public int y;
}
public class Solution {
public static boolean isSafe(int x, int y, int r, int c) {
return (x >= 0) && (x < r) && (y >= 0) && (y < c);
}
public static boolean isFreshOrageLeft(int[][] grid) {
int r = grid.length;
int c = grid[0].length;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == 1)
return true;
}
}
return false;
}
public static int orangesRotting(int[][] grid) {
int r = grid.length;
int c = grid[0].length;
int count = 0;
boolean flag = false;
Queue<Pair> q = new LinkedList<>();
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == 2)
q.add(new Pair(i, j));
}
}
q.add(new Pair(-1, -1));
while (!q.isEmpty()) {
while (q.peek().x != -1 && q.peek().y != -1) {
Pair p = q.poll();
int leftX = p.x - 1;
int leftY = p.y;
if (isSafe(leftX, leftY, r, c) && grid[leftX][leftY] == 1) {
if (!flag) {
count++;
flag = true;
}
grid[leftX][leftY] = 2;
q.add(new Pair(leftX, leftY));
}
int rightX = p.x + 1;
int rightY = p.y;
if (isSafe(rightX, rightY, r, c) && grid[rightX][rightY] == 1) {
if (!flag) {
count++;
flag = true;
}
grid[rightX][rightY] = 2;
q.add(new Pair(rightX, rightY));
}
int upX = p.x;
int upY = p.y + 1;
if (isSafe(upX, upY, r, c) && grid[upX][upY] == 1) {
if (!flag) {
count++;
flag = true;
}
grid[upX][upY] = 2;
q.add(new Pair(upX, upY));
}
int downX = p.x;
int downY = p.y - 1;
if (isSafe(downX, downY, r, c) && grid[downX][downY] == 1) {
if (!flag) {
count++;
flag = true;
}
grid[downX][downY] = 2;
q.add(new Pair(downX, downY));
}
}
flag = false;
q.poll();
if (!q.isEmpty())
q.add(new Pair(-1, -1));
}
return isFreshOrageLeft(grid)?-1:count;
}
public static void main(String[] args) {
int[][] grid = {{2,2,0,1}};
System.out.println(orangesRotting(grid));
}
}