NC398. 腐烂的苹果
描述
示例1
输入:
[[2,1,1],[1,0,1],[1,1,1]]
输出:
4
示例2
输入:
[[2,1,0],[1,0,1],[0,0,0]]
输出:
-1
C++ 解法, 执行用时: 81ms, 内存消耗: 11244KB, 提交时间: 2022-08-06
class Solution {
public:
int rotApple(vector<vector<int> >& grid)
{
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,-1,1};
queue<int>q;
int n=grid.size(),m=grid[0].size(),x,y,ans=0,px,py;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]==2)
{
q.push(i),q.push(j);
}
}
}
while(!q.empty())
{
int s=q.size()/2,flag=0;
for(int i=0;i<s;i++)
{
x=q.front();q.pop();
y=q.front();q.pop();
for(int j=1;j<=4;j++)
{
px=x+dx[j],py=y+dy[j];
if(px>=0&&px<n&&py>=0&&py<m)
{
if(grid[px][py]==1)
{
grid[px][py]=2;
q.push(px),q.push(py);
flag=1;
}
}
}
}
if(flag>0)ans++;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]==1)return -1;
}
}
return ans;
}
};
C++ 解法, 执行用时: 82ms, 内存消耗: 15220KB, 提交时间: 2022-07-29
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型vector<vector<>>
* @return int整型
*/
int rotApple(vector<vector<int> >& grid) {
// write code here
//用递归则是深度优先搜索，用队列则是广度优先搜索
queue<int> bad;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]==2)
{
bad.push(i);
bad.push(j);
grid[i][j]=-1;//标记
}
}
}
help(grid,bad);
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 maxx;
}
void help(vector<vector<int> >& grid,queue<int> qe)
{
int cnt=-1;
while(!qe.empty())
{
cnt++;
int size=qe.size()/2;
for(int i=0;i<size;i++)
{
int curx=qe.front();
qe.pop();
int cury=qe.front();
qe.pop();
if((curx-1>=0)&&(grid[curx-1][cury]>0))
{
qe.push(curx-1);
qe.push(cury);
grid[curx-1][cury]=-1;//访问标记,push后立刻给访问标记，防止相同苹果多次入队
}
if((curx+1<grid.size())&&(grid[curx+1][cury]>0))
{
qe.push(curx+1);
qe.push(cury);
grid[curx+1][cury]=-1;//访问标记
}
if((cury-1>=0)&&(grid[curx][cury-1]>0))
{
qe.push(curx);
qe.push(cury-1);
grid[curx][cury-1]=-1;//访问标记
}
if((cury+1<grid[0].size())&&(grid[curx][cury+1]>0))
{
qe.push(curx);
qe.push(cury+1);
grid[curx][cury+1]=-1;//访问标记
}
}
}
maxx=max(maxx,cnt);
}
private:
int maxx=-1;
};
C++ 解法, 执行用时: 84ms, 内存消耗: 15172KB, 提交时间: 2022-07-13
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型vector<vector<>>
* @return int整型
*/
int rotApple(vector<vector<int> >& grid) {
// write code here
//用递归则是深度优先搜索，用队列则是广度优先搜索
queue<int> bad;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]==2)
{
bad.push(i);
bad.push(j);
grid[i][j]=-1;//标记
}
}
}
help(grid,bad);
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 maxx;
}
void help(vector<vector<int> >& grid,queue<int> qe)
{
int cnt=-1;
while(!qe.empty())
{
cnt++;
int size=qe.size()/2;
for(int i=0;i<size;i++)
{
int curx=qe.front();
qe.pop();
int cury=qe.front();
qe.pop();
if((curx-1>=0)&&(grid[curx-1][cury]>0))
{
qe.push(curx-1);
qe.push(cury);
grid[curx-1][cury]=-1;//访问标记,push后立刻给访问标记，防止相同苹果多次入队
}
if((curx+1<grid.size())&&(grid[curx+1][cury]>0))
{
qe.push(curx+1);
qe.push(cury);
grid[curx+1][cury]=-1;//访问标记
}
if((cury-1>=0)&&(grid[curx][cury-1]>0))
{
qe.push(curx);
qe.push(cury-1);
grid[curx][cury-1]=-1;//访问标记
}
if((cury+1<grid[0].size())&&(grid[curx][cury+1]>0))
{
qe.push(curx);
qe.push(cury+1);
grid[curx][cury+1]=-1;//访问标记
}
}
}
maxx=max(maxx,cnt);
}
private:
int maxx=-1;
};
C++ 解法, 执行用时: 84ms, 内存消耗: 15224KB, 提交时间: 2022-07-02
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型vector<vector<>>
* @return int整型
*/
int rotApple(vector<vector<int> >& grid) {
// write code here
//用递归则是深度优先搜索，用队列则是广度优先搜索
queue<int> bad;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]==2)
{
bad.push(i);
bad.push(j);
grid[i][j]=-1;//标记
}
}
}
//return bad.size();
help(grid,bad);
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 maxx;
}
void help(vector<vector<int> >& grid,queue<int> qe)
{
int cnt=-1;
while(!qe.empty())
{
cnt++;
int size=qe.size()/2;
for(int i=0;i<size;i++)
{
int curx=qe.front();
qe.pop();
int cury=qe.front();
qe.pop();
if((curx-1>=0)&&(grid[curx-1][cury]>0))
{
qe.push(curx-1);
qe.push(cury);
grid[curx-1][cury]=-1;//访问标记,push后立刻给访问标记，防止相同苹果多次入队
}
if((curx+1<grid.size())&&(grid[curx+1][cury]>0))
{
qe.push(curx+1);
qe.push(cury);
grid[curx+1][cury]=-1;//访问标记
}
if((cury-1>=0)&&(grid[curx][cury-1]>0))
{
qe.push(curx);
qe.push(cury-1);
grid[curx][cury-1]=-1;//访问标记
}
if((cury+1<grid[0].size())&&(grid[curx][cury+1]>0))
{
qe.push(curx);
qe.push(cury+1);
grid[curx][cury+1]=-1;//访问标记
}
}
}
maxx=max(maxx,cnt);
}
private:
int maxx=-1;
};
C++ 解法, 执行用时: 86ms, 内存消耗: 11308KB, 提交时间: 2022-07-09
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型vector<vector<>>
* @return int整型
*/
int row, col;
int res = INT_MAX;
queue<pair<int , int>> badq;
int rotApple(vector<vector<int> >& grid) {
// write code here
row = grid.size();
col = grid[0].size();
for(int i = 0; i < row; i ++){
for(int j = 0; j < col; j ++){
if(grid[i][j] == 2){
badq.push({i,j});
}
}
}
int res = bfs(grid);
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 res;
}
int bfs(vector<vector<int>>&grid){
int res = 0;
while(!badq.empty()){
int size = badq.size();
// int cont = 0;
res ++;
while (size --){
auto xypair = badq.front();
badq.pop();
int i = xypair.first;
int j = xypair.second;
grid[i][j] = 2;
if(i - 1 >= 0 && grid[i - 1][j] == 1){
badq.push({i - 1, j});
grid[i - 1][j] = 2;
}
if(j - 1 >= 0 && grid[i][j - 1] == 1){
badq.push({i, j - 1});
grid[i][j - 1] = 2;
}
if(i + 1 < row && grid[i + 1][j] == 1){
badq.push({i + 1, j});
grid[i + 1][j] = 2;
}
if(j + 1 < col && grid[i][j + 1] == 1){
badq.push({i , j + 1});
grid[i][j + 1] = 2;
}
}
}
return res - 1;
}
// int dfs(vector<vector<int>> &grid, int i, int j, int m){
// if(i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == -1 || grid[i][j] == 0) return 0;
// m ++;
// grid[i][j] = -1;
// res = min(res, m);
// dfs(grid, i - 1, j, m);
// dfs(grid, i, j - 1, m);
// dfs(grid, i + 1, j, m);
// dfs(grid, i, j + 1, m);
// }
};