fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node
  5. {
  6. 	int x,y,px,py;
  7. };
  8.  
  9. node troll(int x, int y, int px, int py)
  10. {
  11. 	node t;
  12. 	t.x=x;
  13. 	t.y=y;
  14. 	t.px=px;
  15. 	t.py=py;
  16. 	return t;
  17. }
  18.  
  19. int main()
  20. {
  21. 	//freopen("input.txt","r",stdin);
  22. 	ios_base::sync_with_stdio(false);
  23. 	int m,n;
  24. 	cin>>m>>n;
  25. 	char a[m][n];
  26. 	int temp,temp2;
  27. 	queue<node> q;
  28. 	for(temp=0;temp<m;temp++)
  29. 	{
  30. 		for(temp2=0;temp2<n;temp2++)
  31. 		{
  32. 			cin>>a[temp][temp2];
  33. 			if(a[temp][temp2]=='#')
  34. 			{
  35. 				if(q.empty())
  36. 				{
  37. 					q.push(troll(temp,temp2,-1,-1));
  38. 				}
  39. 			}
  40. 		}
  41. 	}
  42. 	bool visited[m][n];
  43. 	int movex[]={1,-1,0,0},movey[]={0,0,1,-1};
  44. 	memset(visited,0,sizeof(visited));
  45. 	for(int tmp=0;tmp<2;tmp++)
  46. 	{
  47. 		pair<int,int> parent[m][n];
  48. 		//printf("size of queue = %d\n",q.size());
  49. 		while(!q.empty())
  50. 		{
  51.  
  52. 			node t=q.front();
  53. 			q.pop();
  54. 			int x=t.x,y=t.y,px=t.px,py=t.py;
  55. 			//printf("bfs(%d %d)\n",x,y);
  56. 			if((x<0)||(x>=m)||(y<0)||(y>=n))	continue;
  57. 			if(visited[x][y])	continue;
  58. 			visited[x][y]=true;
  59. 			parent[x][y]=make_pair(px,py);
  60. 			//printf("parent (%d,%d) = (%d,%d)\n",x,y,px,py);
  61. 			for(int temp=0;temp<4;temp++)
  62. 			{
  63. 				int nx=x+movex[temp],ny=y+movey[temp];
  64. 				q.push(troll(nx,ny,x,y));
  65. 			}
  66. 		}
  67. 		bool paint[m][n];
  68. 		memset(paint,false,sizeof(paint));
  69. 		memset(visited,false,sizeof(visited));
  70. 		for(temp=0;temp<m;temp++)
  71. 		{
  72. 			for(temp2=0;temp2<n;temp2++)
  73. 			{
  74. 				if(a[temp][temp2]=='#')
  75. 				{
  76. 					int tm=temp,tn=temp2;
  77. 					//printf("start = (%d,%d)\n",tm,tn);
  78. 					while((tm!=-1)&&(tn!=-1))
  79. 					{
  80. 						if(visited[tm][tn])	break;
  81. 						//printf("goto (%d,%d)\n",tm,tn);
  82. 						paint[tm][tn]=true;
  83. 						visited[tm][tn]=true;
  84. 						int ttm=parent[tm][tn].first;
  85. 						int ttn=parent[tm][tn].second;
  86. 						tm=ttm;
  87. 						tn=ttn;
  88. 					}
  89. 				}
  90. 			}
  91. 		}
  92. 		for(temp=0;temp<m;temp++)
  93. 		{
  94. 			for(temp2=0;temp2<n;temp2++)
  95. 			{
  96. 				if(paint[temp][temp2])
  97. 				{
  98. 					cout<<'#';
  99. 				}
  100. 				else
  101. 				{
  102. 					cout<<'.';
  103. 				}
  104. 				if(a[temp][temp2]=='#')
  105. 				{
  106. 					visited[temp][temp2]=false;
  107. 					if(q.empty())
  108. 					{
  109. 						q.push(troll(temp,temp2,-1,-1));
  110. 					}
  111. 				}
  112. 			}
  113. 			cout<<"\n";
  114. 		}
  115. 		if(tmp==0)
  116. 			cout<<"\n";
  117. 	}
  118.  
  119.  
  120. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
7 13
.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#.###.###.
.............
stdout
copy 
.............
.###########.
.#########...
.#########...
.#########...
.###########.
.............

.#########...
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#.###.###.
.#########...
https://ideone.com/whuoRY
language:
C++14 (gcc 8.3)
created:
8 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!