fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int oo = 1e9 + 7;
  5. const int N = 100 + 7;
  6.  
  7. int n, m;
  8. char c[N][N];
  9. bool vis[N][N];
  10. pair<int, int>par[N][N];
  11.  
  12. int dx[] = {-1, 1, 0, 0};
  13. int dy[] = {0, 0, -1, 1};
  14.  
  15. void bfs(int si, int sj){
  16.     queue<pair<int ,int>>q;
  17.     q.push({si, sj});
  18.  
  19.     vis[si][sj] = 1;
  20.     par[si][sj] = {si, sj};
  21.  
  22.     while(!q.empty()){
  23.         auto [u, v] = q.front();
  24.         q.pop();
  25.  
  26.         if(u == 1 || u == m || v == 1 || v == n){
  27.             cout << "YES\n";
  28.  
  29.             vector<pair<int, int>>ans;
  30.             pair<int, int>cur = {u, v};
  31.  
  32.             while(true){
  33.                 ans.push_back(cur);
  34.                 if(cur.first == si && cur.second == sj) break;
  35.                 cur = par[cur.first][cur.second];
  36.             }
  37.             reverse(ans.begin(), ans.end());
  38.  
  39.             for(auto [i, j] : ans) cout << i << " " << j << "\n";
  40.  
  41.             exit(0);
  42.         }
  43.  
  44.         for(int i = 0; i < 4; i++){
  45.             int nx = u + dx[i];
  46.             int ny = v + dy[i];
  47.  
  48.             if(!vis[nx][ny] && c[nx][ny] != 'X'){
  49.                 vis[nx][ny] = 1;
  50.                 par[nx][ny] = {u, v};
  51.                 q.push({nx, ny});
  52.             }
  53.         }
  54.     }
  55. }
  56.  
  57. signed main(){
  58.     ios_base::sync_with_stdio(0); cin.tie(0);
  59.  
  60.     cin >> n >> m;
  61.  
  62.     int si = 0, sj = 0;
  63.  
  64.     for(int i=1; i <= n; i++)
  65.         for(int j=1; j <= m; j++){
  66.             cin >> c[i][j];
  67.  
  68.             if(c[i][j] == 'E'){
  69.                 si = i;
  70.                 sj = j;
  71.             }
  72.         }
  73.  
  74.     bfs(si,sj);
  75.  
  76.     cout << "NO";
  77. }
  78.  
  79.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
0 0
https://ideone.com/NAUBJb
language:
C++14 (gcc 8.3)
created:
4 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!