fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define go ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  4. using namespace std;
  5.  
  6. int const N = 51;
  7. int n;
  8. int sx, sy, tx, ty;
  9. char grid[N][N];
  10. bool vis[N][N];
  11. bool is_inside(int x, int y)
  12. {
  13.     if (x < 0 || x >= n)
  14.     {
  15.         return false;
  16.     }
  17.     if (y < 0 || y >= n)
  18.     {
  19.         return false;
  20.     }
  21.     if (grid[x][y] == '1')
  22.     {
  23.         return false;
  24.     }
  25.     return true;
  26. }
  27. int cost(int x1, int y1, int x2, int y2)
  28. {
  29.     return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  30. }
  31. void dfs(int x, int y, vector<pair<int, int>> &v)
  32. {
  33.     vis[x][y] = true;
  34.     v.push_back({x, y});
  35.     int i[] = {-1, 1, 0, 0};
  36.     int j[] = {0, 0, 1, -1};
  37.     for (int k = 0; k < 4; k++)
  38.     {
  39.         if (is_inside(x + i[k], y + j[k]) && !vis[x + i[k]][y + j[k]])
  40.         {
  41.             dfs(x + i[k], y + j[k], v);
  42.         }
  43.     }
  44. }
  45. void solve()
  46. {
  47.     cin >> n;
  48.     cin >> sx >> sy;
  49.     cin >> tx >> ty;
  50.     for (int i = 0; i < n; i++)
  51.     {
  52.         for (int j = 0; j < n; j++)
  53.         {
  54.             cin >> grid[i][j];
  55.         }
  56.     }
  57.     vector<pair<int, int>> set1, set2;
  58.     dfs(sx - 1, sy - 1, set1);
  59.     dfs(tx - 1, ty - 1, set2);
  60.     int ans = 1e9;
  61.     for (pair<int, int> v1 : set1)
  62.     {
  63.         for (pair<int, int> v2 : set2)
  64.         {
  65.             ans = min(ans, cost(v1.first, v1.second, v2.first, v2.second));
  66.         }
  67.     }
  68.     cout << ans;
  69. }
  70.  
  71. int main()
  72. {
  73.     int t = 1;
  74.     // cin>>t;
  75.     // go;
  76.     while (t--)
  77.     {
  78.         solve();
  79.         cout << "\n";
  80.     }
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 5484KB
comments (?)
stdin 
5
1 1
5 5
00001
11111
00111
00110
00110
stdout 
10
https://ideone.com/hLexCd
language:
C++ (gcc 8.3)
created:
2 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!