fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define endl "\n"
  5. #define F first
  6. #define S second
  7. #define loop(a,n) for(int i=a; i<=n ; i++)
  8. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  9. #define NAME ""
  10. using namespace std;
  11. const int maxx = 1005;
  12. int n, m;
  13. char a[maxx][maxx];
  14. int dist[maxx][maxx];
  15. bool visited[maxx][maxx];
  16. pair<int, int> start, endp;
  17.  
  18. int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
  19. int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};
  20. bool check(int x, int y) {
  21.     return x >= 0 && x < n && y >= 0 && y < m && a[x][y] != '#' && !visited[x][y];
  22. }
  23. int bfs(pair<int, int> src, pair<int, int> dest) {
  24.     queue<pair<int, int>> q;
  25.     q.push(src);
  26.     visited[src.F][src.S] = true;
  27.     dist[src.F][src.S] = 0;
  28.     while (!q.empty()) {
  29.         pair<int, int> u = q.front(); q.pop();
  30.         int x = u.F, y = u.S;
  31.         if (u == dest) return dist[x][y];
  32.         for (int i = 0; i < 8; ++i) {
  33.             int nx = x + dx[i], ny = y + dy[i];
  34.             if (check(nx, ny)) {
  35.                 visited[nx][ny] = true;
  36.                 dist[nx][ny] = dist[x][y] + 1;
  37.                 q.push({nx, ny});
  38.             }
  39.         }
  40.     }
  41.     return -1; 
  42. }
  43.  
  44. int main(){
  45.     ios_base::sync_with_stdio(0);
  46.     cin.tie(0); cout.tie(0);
  47.     //freopen(NAME".INP","r",stdin);
  48.     //freopen(NAME".OUT","w",stdout);
  49.     cin >> n >> m;
  50.     for (int i = 0; i < n; ++i) {
  51.         cin >> a[i];
  52.         for (int j = 0; j < m; ++j) {
  53.             if (a[i][j] == 'S') start = {i, j};
  54.             if (a[i][j] == 'E') endp = {i, j};
  55.         }
  56.     }
  57.     cout << bfs(start, endp);
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JB32Vr
language:
C++ (gcc 8.3)
created:
14 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!