fork download 
  1. #include<bits/stdc++.h>
  2. #define PB push_back
  3. #define F first 
  4. #define S second
  5. using namespace std;
  6. bool tab[2002][2002],odw[2002][2002];
  7. char x;
  8. int sr,n,m;
  9.  
  10. void dfs(pair<int,int>i){
  11. //	if(sr==3)cout<<i<<" "<<j<<endl;
  12. 	odw[i.F][i.S]=1;
  13. 	if(tab[i.F-1][i.S]==0&&odw[i.F-1][i.S]==0) dfs({i.F-1,i.S});
  14. 	if(tab[i.F+1][i.S]==0&&odw[i.F+1][i.S]==0) dfs({i.F+1,i.S});
  15. 	if(tab[i.F][i.S-1]==0&&odw[i.F][i.S-1]==0) dfs({i.F,i.S-1});
  16. 	if(tab[i.F][i.S+1]==0&&odw[i.F][i.S+1]==0&&i.S<n-sr) dfs({i.F,i.S+1});
  17. }
  18.  
  19. bool odp(){
  20. 	for(int i=0;i<=n;i++){
  21. 		for(int j=0;j<=m;j++) odw[j][i]=0;
  22. 	}
  23. 	for(int i=1;i<=n-sr;i++){
  24. 		if(odw[1][i]==0&&tab[1][i]==0) dfs({1,i});
  25. 	}
  26. 	for(int i=1;i<=n;i++){
  27. 		if(odw[m][i]==1) return 0;
  28. 	}
  29. 	return 1;
  30. }
  31.  
  32. int main(){
  33. 	ios_base::sync_with_stdio(0);
  34. 	cin.tie(0);
  35. 	cin>>n>>m;
  36. 	for(int i=0;i<=n+1;i++){
  37. 		for(int j=0;j<=m+1;j++){
  38. 			if(i==0||j==0||j==m+1||i==n+1) tab[j][i]=1;
  39. 			else{
  40. 				cin>>x;
  41. 				if(x=='.') tab[j][i]=0;
  42. 				else tab[j][i]=1;
  43. 			}
  44. 		}
  45. 	}
  46. 	int p=-1,k=2001;
  47. 	while(k-p>1){
  48. 		sr=(p+k)/2;
  49. 		if(odp()==0) p=sr;
  50. 		else k=sr;
  51. 	}
  52. 	if(p==-1) {
  53. 		cout<<"NIE";
  54. 		return 0;
  55. 	}
  56. 	cout<<p;
  57. }
  58.  
Success #stdin #stdout 0.01s 5720KB
comments (?)
stdin 
5 6
#...#.
..##..
#....#
##...#
##..##
stdout 
2
https://ideone.com/Ifunz4
language:
C++ (gcc 8.3)
created:
15 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!