fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  5. #define fs first
  6. #define sn second
  7. #define pb push_back
  8. #define all(v) v.begin(),v.end()
  9. #define sz(v) ((int)v.size())
  10. #define zero(v) memset(v, 0, sizeof(v))
  11. #define forr(i,a,b) for(int i=(a); i<(b); i++)
  12. #define forn(i,n) forr(i,0,n)
  13. #define dforn(i,n) for(int i=n-1; i>=0; i--)
  14. typedef long long ll;
  15. typedef pair<int,int> ii;
  16. typedef vector<int> vi;
  17.  
  18. int n;
  19. char b[55][55];
  20. ii E, S;
  21. vector<ii> lista[55][55];
  22. vector<ii> seg;
  23. bool used[55][55] ;
  24. set<ii> comp, star, final;
  25. ii u;
  26.  
  27. void dfs(ii v) {
  28.     used[v.fs][v.sn] = true ;
  29.     comp.insert(v);
  30.     for (auto j:lista[v.fs][v.sn]) {
  31.         ii to = j;
  32.         if (!used[j.fs][j.sn])
  33.             dfs(to);
  34.     }
  35. }
  36.  
  37. void find_comps(){
  38.     for (auto i:seg)
  39.         used[i.fs][i.sn] = false;
  40.     for (auto i:seg)
  41.         if (!used[i.fs][i.sn]) {
  42.             comp.clear();
  43.             dfs(i);
  44.             /* cout << "Component:" ;
  45.             for (auto j:comp) cout << ' ' <<"("<<j.fs<<","<<j.sn<<")";
  46.             cout<<'\n'; */
  47.             if(comp.find(E)!=comp.end()) star=comp;
  48.             if(comp.find(S)!=comp.end()) final=comp;
  49.         }
  50. }
  51.  
  52. int main(){
  53. 	cin>>n;
  54. 	cin>>E.fs>>E.sn>>S.fs>>S.sn;
  55. 	E.fs-=1;
  56. 	E.sn-=1;
  57. 	S.fs-=1;
  58. 	S.sn-=1;
  59. 	forn(i,n){
  60. 		forn(j,n) cin>>b[i][j];
  61. 	}
  62. 	/* forn(i,n){
  63. 		forn(j,n) cout<<b[i][j]<<" ";
  64. 		cout<<'\n';
  65. 	} */
  66. 	forn(i,n){
  67. 		forn(j,n){
  68. 			if(b[i][j]=='0'){
  69. 				seg.pb({i,j});
  70. 				if(i>0&&b[i-1][j]=='0') lista[i-1][j].pb({i,j}), lista[i][j].pb({i-1,j});
  71. 				if(j>0&&b[i][j-1]=='0') lista[i][j-1].pb({i,j}), lista[i][j].pb({i,j-1});
  72. 			}
  73. 		}
  74. 	}
  75. 	/* for(auto i:seg){
  76. 		cout<<"("<<i.fs<<","<<i.sn<<")";
  77. 		for(auto j:lista[i.fs][i.sn]) cout<<"("<<j.fs<<","<<j.sn<<")";
  78. 		cout<<'\n';
  79. 	} */
  80. 	find_comps();
  81. 	/* for (auto j:star) cout << ' ' <<"("<<j.fs<<","<<j.sn<<")";
  82. 	cout<<'\n';
  83. 	for (auto j:final) cout << ' ' <<"("<<j.fs<<","<<j.sn<<")"; */
  84. 	if(star==final) cout<<0;
  85. 	else{
  86. 		int bridge=10000, aux;
  87. 		for(auto i:star){
  88. 			for(auto j:final){
  89. 				aux=pow((i.fs+1)-(j.fs+1),2)+pow((i.sn+1)-(j.sn+1),2);
  90. 				if(aux<bridge) bridge=aux;
  91. 			}
  92. 		}
  93. 		cout<<bridge;
  94. 	}
  95. 	return 0;
  96. }
  97.  
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
3
1 3
3 1
010
101
010
stdout
copy 
8
https://ideone.com/bFu7tA
language:
C++ (gcc 8.3)
created:
4 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!