Untitled
unknown
plain_text
a year ago
1.4 kB
2
Indexable
Never
int i,j; int m=grid.size(),n=grid[0].size(); int visited[m][n]; queue<pair<pair<int,int>,int>>q; for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(grid[i][j]==2) { visited[i][j]=2; q.push({{i,j},0}); } else { visited[i][j]=0; } } } int res=0; int row[]={-1,0,+1,0}; int col[]={0,+1,0,-1}; while(!q.empty()) { int r=q.front().first.first; int c=q.front().first.second; int t=q.front().second; res=max(t,res); q.pop(); for(i=0;i<4;i++) { int nr=r+row[i]; int nc=c+col[i]; if(nr<m && nc<n && nr>=0 && nc>=0 && visited[nr][nc]!=2 && grid[nr][nc]==1) { q.push({{nr,nc},t+1}); visited[nr][nc]=1; } } } for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(visited[i][j]!=2 && grid[i][j]==1) return -1; } } return res;