fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. int h, w, q;
  9. vector<string> grid;
  10.  
  11. int dx[] = {-1, 1, 0, 0};
  12. int dy[] = {0, 0, -1, 1};
  13.  
  14. bool bfs(int sx, int sy, int ex, int ey, set<pair<int, int>>& blocked) {
  15.     queue<pair<int, int>> q;
  16.     set<pair<int, int>> visited;
  17.     q.push({sx, sy});
  18.     visited.insert({sx, sy});
  19.  
  20.     while (!q.empty()) {
  21.         auto [x, y] = q.front(); q.pop();
  22.  
  23.         if (x == ex && y == ey) return true;
  24.  
  25.         for (int i = 0; i < 4; ++i) {
  26.             int nx = x + dx[i], ny = y + dy[i];
  27.             if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] == '.' && !blocked.count({nx, ny}) && !visited.count({nx, ny})) {
  28.                 visited.insert({nx, ny});
  29.                 q.push({nx, ny});
  30.             }
  31.         }
  32.     }
  33.     return false;
  34. }
  35.  
  36. int main() {
  37.     ios::sync_with_stdio(false);
  38.     cin.tie(nullptr);
  39.  
  40.     cin >> h >> w >> q;
  41.     grid.resize(h);
  42.  
  43.     for (int i = 0; i < h; ++i) {
  44.         cin >> grid[i];
  45.     }
  46.  
  47.     while (q--) {
  48.         int k;
  49.         cin >> k;
  50.         set<pair<int, int>> blocked;
  51.  
  52.         for (int i = 0; i < k; ++i) {
  53.             int r, c;
  54.             cin >> r >> c;
  55.             blocked.insert({r - 1, c - 1});
  56.         }
  57.  
  58.         bool forward = bfs(0, 0, h - 1, w - 1, blocked);
  59.         bool backward = bfs(h - 1, w - 1, 0, 0, blocked);
  60.  
  61.         if (forward && backward) {
  62.             cout << "YES\n";
  63.         } else {
  64.             cout << "NO\n";
  65.         }
  66.         cout.flush(); 
  67.     }
  68.  
  69.     return 0;
  70. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
3 5 4
.....
.....
.#...
1
1 4
1
1 5
2
2 4
3 1
2
1 5
3 3
stdout
copy 
YES
YES
YES
YES
https://ideone.com/FTe2pg
language:
C++ (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!