fork download
copy 
  1. #include <iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. #include<string>
  5. #define MAX 200
  6. using namespace std;
  7.  
  8. int n, m;
  9. int output_grid[200][200];
  10. char input_grid[200][200];
  11.  
  12. struct node{
  13. 	int x;
  14. 	int y;
  15. 	int dist;
  16. 	};
  17.  
  18.  
  19. void bfs(){
  20. 	queue<node> q;
  21. 	bool visited[MAX][MAX];
  22. 	int x,y;
  23.  
  24. 	for(int i=0;i<m;i++)
  25. 		for(int j=0;j<n;j++)
  26. 			visited[i][j]=false;
  27. 	node temp,temp1;
  28. 	for(int i=0;i<m;i++){
  29. 		for(int j=0;j<n;j++){
  30. 			if(input_grid[i][j]=='1'){
  31. 				visited[i][j]=true;
  32. 				temp.x=i;
  33. 				temp.y=j;
  34. 				temp.dist=0;
  35. 				q.push(temp);
  36. 			}
  37. 		}
  38. 	}
  39.  
  40. 	while(!q.empty()){
  41. 		temp=q.front();
  42. 		q.pop();
  43. 		output_grid[temp.x][temp.y] = temp.dist;
  44.  
  45. 		//check for bounds before pushing
  46.  
  47. 		if(temp.y-1 >=0 && !visited[temp.x][temp.y-1]){
  48. 			temp1.x = temp.x;
  49. 			temp1.y = temp.y-1;
  50. 			temp1.dist = temp.dist+1;
  51. 			q.push(temp1);
  52. 			visited[temp1.x][temp1.y]=true;
  53. 		}
  54.  
  55. 		if(temp.x-1 >=0 && !visited[temp.x-1][temp.y]){
  56. 			temp1.x = temp.x-1;
  57. 			temp1.y = temp.y;
  58. 			temp1.dist = temp.dist+1;
  59. 			q.push(temp1);
  60. 			visited[temp1.x][temp1.y]=true;
  61. 		}
  62.  
  63. 		if(temp.y+1 <=n && !visited[temp.x][temp.y+1]){
  64. 			temp1.x = temp.x;
  65. 			temp1.y = temp.y+1;
  66. 			temp1.dist = temp.dist+1;
  67. 			q.push(temp1);
  68. 			visited[temp1.x][temp1.y]=true;
  69. 		}
  70.  
  71. 		if(temp.x+1 <=m && !visited[temp.x+1][temp.y]){
  72. 			temp1.x = temp.x+1;
  73. 			temp1.y = temp.y;
  74. 			temp1.dist = temp.dist+1;
  75. 			q.push(temp1);
  76. 			visited[temp1.x][temp1.y]=true;
  77. 		}
  78.  
  79. 	}
  80.  
  81.  
  82. }
  83.  
  84. int main() {
  85. 	int cases;
  86. 	scanf("%d",&cases);
  87. 	while(cases--){
  88. 		char temp[200];
  89. 		scanf("%d %d",&m,&n);
  90. 		for(int i=0;i<m;i++){
  91. 				scanf("%s",temp);
  92. 				for(int j=0;j<n;j++){
  93. 					input_grid[i][j]=temp[j];
  94. 				}
  95. 		}
  96.  
  97. 		bfs();			
  98. 		for(int i=0;i<m;i++){
  99. 			for(int j=0;j<n;j++)
  100. 				printf("%d ",output_grid[i][j]);
  101. 			printf("\n");
  102. 		}
  103. 	}
  104. 	return 0;
  105. }
Success #stdin #stdout 0s 3656KB
comments (?)
stdin
copy 
1
10 10
0001001010
0001001010
0001001010
0001001010
0001001010
0001001010
0001001010
0001001010
0001001010
0001001010
stdout
copy 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1 
3 2 1 0 1 1 0 1 0 1
https://ideone.com/UKhfKA
language:
C++ (gcc 8.3)
created:
10 years 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!