fork download
copy 
  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. vector<vector<int> > a, used, dist;
  7. vector<vector<pair<int,int> > > par;
  8. int n,m;
  9. void bfs(){
  10. 	queue<pair<int,int> > q;
  11. 	for(int i=0; i<n; i++)
  12. 		for(int j=0; j<m; j++){
  13. 			if(a[i][j]==1){
  14. 				q.push({i,j});
  15. 				used[i][j]=1;
  16. 			}
  17. 		}
  18. 	while(!q.empty()){
  19. 		pair<int,int> u=q.front();
  20. 		q.pop();
  21. 		int x=u.first, y=u.second;
  22. 		int dx[4]={-1,0,1, 0};
  23. 		int dy[4]={ 0,1,0,-1};
  24. 		for(int i=0;i<4;i++){
  25. 			int l=x+dx[i], r=y+dy[i];
  26. 			if(l>=0 and l<=n-1 and r>=0 and r<=m-1 and used[l][r]==0){
  27. 				used[l][r]=1;
  28. 				dist[l][r]=dist[x][y]+1;
  29. 				par[l][r]={x,y};
  30. 				q.push({l,r});
  31. 			}
  32. 		}
  33. 	}
  34. }
  35.  
  36. int main(){
  37. 	cin>>n>>m;
  38. 	a.resize(n,vector<int>(m,0));
  39. 	used.resize(n,vector<int>(m,0));
  40. 	dist.resize(n,vector<int>(m,0));
  41. 	par.resize(n,vector<pair<int,int> >(m,{-1,-1}));
  42. 	for(int i=0; i<n; i++)
  43. 		for(int j=0; j<m; j++)
  44. 			cin>>a[i][j];
  45. 	bfs();
  46. 	for(int i=0; i<n; i++){
  47. 		for(int j=0; j<m; j++)
  48. 			cout<<dist[i][j]<<" ";
  49. 		cout<<endl;
  50. 	}
  51. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
2 3
0 0 1
1 0 0
stdout
copy 
1 1 0 
0 1 1
https://ideone.com/MNwJtC
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!