[994] Rotting Oranges

我竟然有能力處理爛橘子了！！！（感動落淚）

雖然好像不是很正確的解法（嗎）等我再多寫幾題BFS 再回來看好了  XD

有一些麻煩的tricky ?! 用了一個temp matrix 去暫存每一輪新爛掉的橘子，

跑完這一round 後，再把它copy回去原本的grid array，但要特別處理：

"這一輪爛掉但是可能被加超過一次的橘子" 所以這種橘子要填2，代表下一次要處理它的周邊

（原本的寫法可能會變成3,4，那下輪就會忽略掉它了。）

另外使用了count 先算一次最開始有幾顆好橘子，接著再每一round 做完後再算一次，

如果數目一樣，就可以break出來了。根據題意，如果好橘子還有剩，就return 負一，完(攤手)

void rotting(int** matrix, int** org, int row, int column, int m, int n)

{

matrix[row][column]++;

if (column+1 < n && org[row][column+1]==1)

matrix[row][column+1]++;

if (column-1 >=0 && org[row][column-1]==1)

matrix[row][column-1]++;

if (row+1 < m && org[row+1][column] == 1)

matrix[row+1][column]++;

if (row-1 >= 0 && org[row-1][column] ==1)

matrix[row-1][column]++;

return;

}

int orangesRotting(int** grid, int gridSize, int* gridColSize){

int ret= -1, count=0;

int m=gridSize, n=(*gridColSize);

int **rotate = calloc (m, sizeof(int *));

for (int i=0;i<m; i++)

rotate[i]= calloc (n, sizeof(int));

for (int i=0;i<m; i++)

for (int j=0; j<n; j++)

{

if (grid[i][j]==1)

count++;

rotate[i][j]=grid[i][j];

}

while(1)

{

ret++;

for (int i=0;i<m; i++)

for (int j=0; j<n; j++)

{

if (grid[i][j]==2)

rotting(rotate, grid ,i,j, m,n);

}

int inner_count =0;

for (int i=0;i<m; i++)

for (int j=0; j<n; j++)

{

if (rotate[i][j] >=2 && grid[i][j]==1)

grid[i][j]=2;

else

grid[i][j]=rotate[i][j];

if (grid[i][j]==1)

inner_count++;

}

if (inner_count == count)

break;

else

count = inner_count;

}

free(rotate);

return (count>0)? (-1):ret;

}