Commit9ed0176

authored

Merge pull requestneetcode-gh#1477 from elcabalero/patch-4

Update rotting_oranges.cpp as in the video

2 parents7342762 +6eee163 commit9ed0176Copy full SHA for 9ed0176

File tree

+46

-1

lines changed

+46

-1

lines changed

Lines changed: 46 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -7,7 +7,7 @@`
`7`	`7`	`Time: O(m x n)`
`8`	`8`	`Space: O(m x n)`
`9`	`9`	`*/`
`10`		`-`
	`10`	`+/*`
`11`	`11`	`class Solution {`
`12`	`12`	`public:`
`13`	`13`	`int orangesRotting(vector<vector<int>>& grid) {`
`@@ -72,3 +72,48 @@ class Solution {`
`72`	`72`	`private:`
`73`	`73`	`vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};`
`74`	`74`	`};`
	`75`	`+*/`
	`76`	`+`
	`77`	`+classSolution {`
	`78`	`+public:`
	`79`	`+intorangesRotting(vector<vector<int>>& grid) {`
	`80`	`+int n = grid.size();`
	`81`	`+int m = grid[0].size();`
	`82`	`+int time =0;`
	`83`	`+int fresh =0;`
	`84`	`+`
	`85`	`+ queue<pair<int,int>> q;`
	`86`	`+`
	`87`	`+ vector<pair<int,int>> directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};`
	`88`	`+`
	`89`	`+for (int i =0; i < n; ++i){`
	`90`	`+for (int j =0; j < m; ++j){`
	`91`	`+if (grid[i][j] ==1)`
	`92`	`+ ++fresh;`
	`93`	`+if (grid[i][j] ==2)`
	`94`	`+ q.push({i,j});`
	`95`	`+ }`
	`96`	`+ }`
	`97`	`+`
	`98`	`+while (!q.empty()and fresh >0){`
	`99`	`+int size = q.size();`
	`100`	`+while (size--){`
	`101`	`+int i = q.front().first;`
	`102`	`+int j = q.front().second;`
	`103`	`+ q.pop();`
	`104`	`+for (auto& [x,y] : directions){`
	`105`	`+int n_i = i + x;`
	`106`	`+int n_j = j + y;`
	`107`	`+if (n_i <0 \|\| n_i >= n \|\| n_j <0 \|\| n_j >= m \|\| grid[n_i][n_j] !=1)`
	`108`	`+continue;`
	`109`	`+ grid[n_i][n_j] =2;`
	`110`	`+ q.push({n_i,n_j});`
	`111`	`+ --fresh;`
	`112`	`+ }`
	`113`	`+ }`
	`114`	`+ ++time;`
	`115`	`+ }`
	`116`	`+`
	`117`	`+return fresh ? -1 : time;`
	`118`	`+ }`
	`119`	`+};`

Comments

(0)