public class Solution
{
int row = ;
int column = ;
int FreshOrangeCount = ;
int RottenOrangeCount = ;
int Minute = ;
Queue<int[]> Q = new Queue<int[]>();
int[,] TagGrid;
public void BFS(int[][] grid)
{
var rottinglist = new List<int[]>(); while(Q.Count>)
{
while (Q.Count > )
{
var orange = Q.Dequeue(); int i = orange[];
int j = orange[]; int i_new = -;
int j_new = -; //合法范围:up,down,left,right
//未访问的:TagGrid[newi,newj]==0
//新鲜的（grid[i][j]==1）
i_new = i - ;
j_new = j; //up:i-1>=0
if (i_new >= && TagGrid[i_new, j_new] == && grid[i_new][j_new] == )
{
FreshOrangeCount--;
RottenOrangeCount++;
TagGrid[i_new, j_new] = ;//visited
grid[i_new][j_new] = ;//go bad
rottinglist.Add(new int[] { i_new, j_new });
} //down:i+1<=row-1
i_new = i + ;
j_new = j;
if (i_new <= row - && TagGrid[i_new, j_new] == && grid[i_new][j_new] == )
{
FreshOrangeCount--;
RottenOrangeCount++;
TagGrid[i_new, j_new] = ;//visited
grid[i_new][j_new] = ;//go bad
rottinglist.Add(new int[] { i_new, j_new });
} //left:j-1>=0
i_new = i;
j_new = j - ;
if (j_new >= && TagGrid[i_new, j_new] == && grid[i_new][j_new] == )
{
FreshOrangeCount--;
RottenOrangeCount++;
TagGrid[i_new, j_new] = ;//visited
grid[i_new][j_new] = ;//go bad
rottinglist.Add(new int[] { i_new, j_new });
} //right:j+1<=column-1
i_new = i;
j_new = j + ;
if (j_new <= column - && TagGrid[i_new, j_new] == && grid[i_new][j_new] == )
{
FreshOrangeCount--;
RottenOrangeCount++;
TagGrid[i_new, j_new] = ;//visited
grid[i_new][j_new] = ;//go bad
rottinglist.Add(new int[] { i_new, j_new });
} }
if (rottinglist.Any())
{
Minute++;
}
foreach (var l in rottinglist)
{
Q.Enqueue(l);
}
rottinglist.Clear();
}
} public int OrangesRotting(int[][] grid)
{
row = grid.Length;
column = grid[].Length;
TagGrid = new int[row, column]; for (var i = ; i < row; i++)
{
for (var j = ; j < column; j++)
{
TagGrid[i, j] = ;//unvisited
if (grid[i][j] == )
{
FreshOrangeCount++;
}
if (grid[i][j] == )
{
RottenOrangeCount++;
Q.Enqueue(new int[] { i, j });
}
}
} BFS(grid); if (FreshOrangeCount != )
{
return -;
}
else
{
return Minute;
}
}
}