当前位置:网站首页>Leetcode 994, rotten orange
Leetcode 994, rotten orange
2022-04-23 20:26:00 【Die in a trap】
994、 Rotten oranges
1) Title Description
In the given m x n
grid grid
in , Each cell can have one of three values :
- value
0
For empty cells ; - value
1
For fresh oranges ; - value
2
For rotten oranges .
Every minute , Rotten oranges Around 4 Adjacent in two directions All fresh oranges rot .
return The minimum number of minutes that must elapse until there are no fresh oranges in the cell . If not , return -1
.
Example 1:
Input :grid = [[2,1,1],[1,1,0],[0,1,1]]
Output :4
Example 2:
Input :grid = [[2,1,1],[0,1,1],[1,0,1]]
Output :-1
explain : Orange in the lower left corner ( The first 2 That's ok , The first 0 Column ) Never rot , Because decay happens only in 4 Positive upward .
Example 3:
Input :grid = [[0,2]]
Output :0
explain : because 0 There are no fresh oranges by minute , So the answer is 0 .
Tips :
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j]
Only for0
、1
or2
2) analysis
Breadth first search .
- Traverse
grid
Where to store all rotten oranges , The team , And count the number of fresh oranges ; - Then traverse the queue , If there are fresh oranges around , Then set the time , Then add it to the queue , Reduce the number of fresh oranges by one ;
- After breadth first search , If the number of fresh oranges is not zero , return
-1
.
3)C++
Code
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m=grid.size();
int n=grid[0].size();
int dx[4]={
1,0,-1,0};
int dy[4]={
0,1,0,-1};
int cnt_1=0;
int res=0;
queue<pair<int,int>> que;
vector<vector<int>> timeCosted(m,vector<int> (n,0));
// Traversing the grid , Record the coordinates of all rotten oranges and the number of fresh oranges
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==2)
que.emplace(i,j);
else if(grid[i][j]==1)
cnt_1++;
}
}
// Breadth first search
while(!que.empty()){
int x=que.front().first;
int y=que.front().second;
que.pop();
for(int i=0;i<4;i++){
int newX=x+dx[i];
int newY=y+dy[i];
if(newX>=0&&newX<m&&newY>=0&&newY<n&&grid[newX][newY]==1&&!timeCosted[newX][newY]){
timeCosted[newX][newY]=timeCosted[x][y]+1;
que.emplace(newX,newY);
if(grid[newX][newY]==1){
res=res>timeCosted[newX][newY]?res:timeCosted[newX][newY];
cnt_1-=1;
if(!cnt_1)
break;
}
}
}
}
return cnt_1?-1:res;
}
};
版权声明
本文为[Die in a trap]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204232023107507.html
边栏推荐
- Still using listview? Use animatedlist to make list elements move
- 論文寫作 19: 會議論文與期刊論文的區別
- Three. Based on ply format point cloud voxel model JS upload interface writing
- PCL点云处理之计算两平面交线(五十一)
- Experience of mathematical modeling in 18 year research competition
- Zdns was invited to attend the annual conference of Tencent cloud basic resources and share the 2020 domain name industry development report
- Mysql database backup scheme
- LeetCode 1351、统计有序矩阵中的负数
- Markdown < a > tag new page open link
- LeetCode 1346、检查整数及其两倍数是否存在
猜你喜欢
ArcGIS JS version military landmark drawing (dovetail arrow, pincer arrow, assembly area) fan and other custom graphics
After route link navigation, the sub page does not display the navigation style problem
[graph theory brush question-4] force deduction 778 Swimming in a rising pool
Operation of numpy array
Click an EL checkbox to select all questions
Devexpress 14.1 installation record
Mathematical modeling column | Part 5: MATLAB optimization model solving method (Part I): Standard Model
Zdns was invited to attend the annual conference of Tencent cloud basic resources and share the 2020 domain name industry development report
Browser - learning notes
Scrapy教程 - (2)寫一個簡單爬蟲
随机推荐
[latex] 5 how to quickly write out the latex formula corresponding to the formula
. Ren -- the intimate artifact in the field of vertical Recruitment!
I JS deep copy and shallow copy
Thirty What are VM and VC?
[stack and queue topics] - sliding window
Error reported by Azkaban: Azkaban jobExecutor. utils. process. ProcessFailureException: Process exited with code 64
Numpy sort search count set
内网渗透之DOS命令
Common form verification
Leetcode dynamic planning training camp (1-5 days)
Numpy Index & slice & iteration
Investigate why close is required after sqlsession is used in mybatties
Solve the Chinese garbled code of URL in JS - decoding
[PTA] l1-006 continuity factor
Azkaban recompile, solve: could not connect to SMTP host: SMTP 163.com, port: 465 [January 10, 2022]
LeetCode 542、01 矩阵
Mysql database backup scheme
Recognition of high-speed road signs by Matlab using alexnet
star
XXXI` Prototype ` displays prototype properties and`__ proto__` Implicit prototype properties