fork download
  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. // Arah gerakan: atas, bawah, kiri, kanan
  12. int dx[] = {-1, 1, 0, 0};
  13. int dy[] = {0, 0, -1, 1};
  14.  
  15. bool bfs(int sx, int sy, int ex, int ey, set<pair<int, int>>& blocked) {
  16. queue<pair<int, int>> q;
  17. set<pair<int, int>> visited;
  18. q.push({sx, sy});
  19. visited.insert({sx, sy});
  20.  
  21. while (!q.empty()) {
  22. auto [x, y] = q.front(); q.pop();
  23.  
  24. if (x == ex && y == ey) return true;
  25.  
  26. for (int i = 0; i < 4; ++i) {
  27. int nx = x + dx[i], ny = y + dy[i];
  28. if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] == '.' && !blocked.count({nx, ny}) && !visited.count({nx, ny})) {
  29. visited.insert({nx, ny});
  30. q.push({nx, ny});
  31. }
  32. }
  33. }
  34. return false;
  35. }
  36.  
  37. bool isInteresting(set<pair<int, int>>& blocked) {
  38. queue<pair<int, int>> q;
  39. set<pair<int, int>> visited;
  40. q.push({0, 0});
  41. visited.insert({0, 0});
  42.  
  43. while (!q.empty()) {
  44. auto [x, y] = q.front(); q.pop();
  45.  
  46. if (x == h - 1 && y == w - 1) {
  47. return bfs(h - 1, w - 1, 0, 0, blocked);
  48. }
  49.  
  50. for (int i = 0; i < 4; ++i) {
  51. int nx = x + dx[i], ny = y + dy[i];
  52. if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] == '.' && !blocked.count({nx, ny}) && !visited.count({nx, ny})) {
  53. visited.insert({nx, ny});
  54. q.push({nx, ny});
  55. }
  56. }
  57. }
  58. return false;
  59. }
  60.  
  61. int main() {
  62. ios::sync_with_stdio(false);
  63. cin.tie(nullptr);
  64.  
  65. cin >> h >> w >> q;
  66. grid.resize(h);
  67.  
  68. for (int i = 0; i < h; ++i) {
  69. cin >> grid[i];
  70. }
  71.  
  72. while (q--) {
  73. int k;
  74. cin >> k;
  75. set<pair<int, int>> blocked;
  76.  
  77. for (int i = 0; i < k; ++i) {
  78. int r, c;
  79. cin >> r >> c;
  80. blocked.insert({r - 1, c - 1});
  81. }
  82.  
  83. cout << (isInteresting(blocked) ? "YES\n" : "NO\n");
  84. cout.flush(); // Flush output as required
  85. }
  86.  
  87. return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 5288KB
stdin
9 31 5
...............................
...............................
.###.###.#.###...###.###.#.###.
...#.#.#.#.#.......#.#.#.#...#.
.###.#.#.#.###...###.#.#.#...#.
.#...#.#.#.#.#...#...#.#.#...#.
.###.###.#.###...###.###.#...#.
...............................
...............................
5
6 5
2 11
1 14
8 15
2 14
5
2 14
1 14
8 16
6 5
2 11
3
2 2
1 4
8 30
10
3 1
3 11
5 16
7 21
4 16
3 5
7 31
3 9
7 25
3 27
10
3 1
3 9
7 25
3 27
7 21
4 17
3 5
7 31
4 16
3 11
stdout
YES
YES
YES
YES
YES