第一次，广度优先算法遍历图，用了两个队列，100%，17.50%
class Solution { public: //广度优先遍历 int dp[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int orangesRotting(vector<vector<int>>& grid) { int count = 0; queue<int> q_x; queue<int> q_y; //初始化 for(int i = 0;i < grid.size();i++){ for(int j = 0;j < grid[0].size();j++){ if(grid[i][j] == 2){ q_x.push(i); q_y.push(j); } } } while(!q_x.empty()){ int n = q_x.size(); for(int i = 0;i < n;i++){ int x = q_x.front(); int y = q_y.front(); q_x.pop(); q_y.pop(); for(int j = 0;j < 4;j++){ if(x + dp[j][0] < grid.size() && x + dp[j][0] >=0 && y + dp[j][1] < grid[0].size() && y + dp[j][1] >=0){ if(grid[x + dp[j][0] ][y + dp[j][1] ] == 1){ q_x.push(x + dp[j][0]); q_y.push(y + dp[j][1]); grid[x + dp[j][0] ][y + dp[j][1] ] = 2; } } } } if(!q_x.empty()) count++; } for(int i = 0;i < grid.size();i++){ for(int j = 0;j < grid[0].size();j++){ if(grid[i][j] == 1){ return -1; } } } return count; } };经评论区点播，可以将坐标（i，j）存储成x = i * column + j ，因为 j < column 所以
i = x /column;j = x % column;
以此降低内存消耗 时间 100%，空间88.79%
class Solution { public: //广度优先 //调用了几次bfs //加入队列，队列值q=i*c+j,其中c是列数 //则i = q/c，j = q%c //最后一次会多记一次 int orangesRotting(vector<vector<int>>& grid) { int row = grid.size(); int column = grid[0].size(); int res = 0; //将初始的腐烂的橘子放入队列中 queue<int> queue; for(int i = 0;i < row;i++) for(int j = 0;j < column;j++) { if(grid[i][j] == 2) queue.push(i*column+j); } //深度优先算法 while(queue.size()){ int n = queue.size(); for(int x = 0;x < n;x++){ int y = queue.front(); queue.pop(); int i = y/column; int j = y%column; //感染周围的橘子，并将其加入队列,上下左右 if((i - 1) >= 0 && grid[i-1][j] == 1){ grid[i-1][j] = 2; queue.push((i-1)*column+j); } if((i+1)<row && grid[i+1][j] == 1){ grid[i+1][j] = 2; queue.push((i+1)*column+j); } if((j-1) >= 0 && grid[i][j-1] == 1){ grid[i][j-1] = 2; queue.push(i*column + j-1); } if((j+1) < column && grid[i][j+1] == 1){ grid[i][j+1] = 2; queue.push(i*column + j+1); } } res++; } //如果有橘子没被感染，返回-1 for(int i = 0;i < row;i++) for(int j = 0;j < column;j++) if(grid[i][j] == 1) return -1; //res = 0,没坏掉的橘子，返回0； if(res == 0) return 0; return res-1; } };
