思路:直接bfs會出現2個腐爛的橘子在兩邊同時進行,這樣會錯誤。
正確思路:每分鐘變化后所有橘子狀態為next_grid,直到橘子狀態不改變。如果狀態不變,且無新鮮的橘子則返回時間,否則返回-1
class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {row=grid.size(), col=grid[0].size();int res=0;vector<vector<int> > next_grid(grid.begin(), grid.end());while(next_min(grid, next_grid)){grid=next_grid;res++;}if(all_rot(grid)) return res;return -1;}
private:int row,col;int vec[4][2]={{-1,0},{1,0},{0,-1},{0,1}};bool next_min(vector<vector<int>>& grid, vector<vector<int>>& next_grid){bool flag=false;//橘子狀態是否變化 for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(grid[i][j]==2){for(int k=0;k<4;k++){int new_x = i + vec[k][0];int new_y = j + vec[k][1];if(new_x<row && new_x>=0 && new_y<col && new_y>=0){if(next_grid[new_x][new_y]==1){next_grid[new_x][new_y]=2;flag=true;}}}}}}return flag;}bool all_rot(vector<vector<int>>& grid){for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(grid[i][j]==1) return false; }}return true;}
};
?
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态