fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define endl '\n'
  6.  
  7. typedef long long int64;
  8. typedef pair<int,int> pii;
  9. typedef vector<int> vi;
  10.  
  11. const int oo = 0x3f3f3f3f;
  12. const double eps = 1e-9;
  13. const int maxn = 1501;
  14.  
  15. struct tgraph{
  16.     int n;
  17.     vector<vector<int>> adj;
  18.  
  19.     tgraph(int n=0) : n(n), adj(n) {}
  20.  
  21.     void add_edge(int u, int v)
  22.     {
  23.         adj[u].push_back(v);
  24.         adj[v].push_back(u);
  25.     }
  26.  
  27.     int add_node()
  28.     {
  29.         adj.push_back({});
  30.         return n++;
  31.     }
  32.  
  33.     vector<int>& operator[](int u) { return adj[u]; }
  34. };
  35.  
  36. struct graph
  37. {
  38.     int n;
  39.     vector<vector<int>> adj;
  40.  
  41.     graph(int n=0) : n(n), adj(n) {}
  42.  
  43.     void add_edge(int u, int v)
  44.     {
  45.         adj[u].push_back(v);
  46.         adj[v].push_back(u);
  47.     }
  48.  
  49.     int add_node()
  50.     {
  51.         adj.push_back({});
  52.         return n++;
  53.     }
  54.  
  55.     vector<int>& operator[](int u) { return adj[u]; }
  56.  
  57.     vector<int> num, low, art, stk, id;
  58.     vector<vector<int>> comps;
  59.  
  60.     tgraph tree;
  61.  
  62.     void biconnected_components()
  63.     {
  64.         num = vector<int>(n);
  65.         low = vector<int>(n);
  66.         art = vector<int>(n);
  67.         stk = vector<int>();
  68.         comps = vector<vector<int>>();
  69.  
  70.         function<void(int, int, int&)> dfs = [&](int u, int p, int &t)
  71.         {
  72.             num[u] = low[u] = ++t;
  73.             stk.push_back(u);
  74.  
  75.             for (int v : adj[u]) if (v != p)
  76.             {
  77.                 if (!num[v])
  78.                 {
  79.                     dfs(v, u, t);
  80.                     low[u] = min(low[u], low[v]);
  81.  
  82.                     if (low[v] >= num[u])
  83.                     {
  84.                         art[u] = (num[u] > 1 || num[v] > 2);
  85.  
  86.                         comps.push_back({u});
  87.                         while (comps.back().back() != v)
  88.                             comps.back().push_back(stk.back()),
  89.                             stk.pop_back();
  90.                     }
  91.                 }
  92.                 else low[u] = min(low[u], num[v]);
  93.             }
  94.         };
  95.  
  96.         for (int u = 0, t; u < n; ++u)
  97.             if (!num[u]) dfs(u, -1, t = 0);
  98.  
  99.         tree = tgraph(0);
  100.         id = vector<int>(n);
  101.  
  102.         for (int u = 0; u < n; ++u)
  103.             if (art[u]) id[u] = tree.add_node();
  104.  
  105.         for (auto &comp : comps)
  106.         {
  107.             int node = tree.add_node();
  108.             for (int u : comp)
  109.                 if (!art[u]) id[u] = node;
  110.                 else tree.add_edge(node, id[u]);
  111.         }
  112.     }
  113.  
  114.     bool connected(int u, int v){
  115.         if (art[u]) swap(u, v);
  116.  
  117.         if (art[u]){
  118.             //art  art
  119.             set<int> X;
  120.  
  121.             for (auto x : tree.adj[ id[v] ])
  122.                 X.insert(x);
  123.  
  124.             for (auto x : tree.adj[ id[u] ])
  125.                 if (X.find(x) != X.end())
  126.                     return true;
  127.  
  128.             return false;
  129.         }
  130.         else if (!art[v]){
  131.             // ~art ~art
  132.             return id[u] == id[v];
  133.         }
  134.         else{
  135.             // ~art art
  136.             for (auto x : tree.adj[ id[v] ]){
  137.                 if (x == id[u])
  138.                     return true;
  139.             }
  140.  
  141.             return false;
  142.         }
  143.     }
  144. };
  145.  
  146. struct pos_t{
  147.     int x, y, k;
  148. };
  149.  
  150. char M[maxn][maxn];
  151. int ID[maxn][maxn];
  152.  
  153. int dx[4] = {0, -1, 0, 1};
  154. int dy[4] = {1, 0, -1, 0};
  155.  
  156. bool vis[maxn][maxn][4];
  157.  
  158. int main(){
  159.     freopen("pushabox.in", "r", stdin);
  160.     freopen("pushabox.out", "w", stdout);
  161.  
  162.     ios_base::sync_with_stdio(0);
  163.     cin.tie(0);
  164.  
  165.     int n, m, q;
  166.  
  167.     cin >> n >> m >> q;
  168.  
  169.     pii A, B;
  170.  
  171.     int total_nodes = 0;
  172.  
  173.     for (int i = 0; i < n; ++i){
  174.         cin >> M[i];
  175.  
  176.         for (int j = 0; j < m; ++j){
  177.             if (M[i][j] == 'A'){
  178.                 A = pii(i,j);
  179.                 M[i][j] = '.';
  180.             }
  181.             else if (M[i][j] == 'B'){
  182.                 B = pii(i,j);
  183.                 M[i][j] = '.';
  184.             }
  185.  
  186.             if (M[i][j] == '.')
  187.                 ID[i][j] = total_nodes++;
  188.         }
  189.     }
  190.  
  191.     graph G(total_nodes);
  192.  
  193.     for (int i = 0; i < n; ++i)
  194.         for (int j = 0; j < m; ++j){
  195.             if (M[i][j] == '.'){
  196.                 if (i && M[i-1][j] == '.')
  197.                     G.add_edge(ID[i][j], ID[i-1][j]);
  198.                 if (j && M[i][j-1] == '.')
  199.                     G.add_edge(ID[i][j], ID[i][j-1]);
  200.             }
  201.         }
  202.  
  203.     G.biconnected_components();
  204.  
  205.     // debug area
  206.  
  207.     // for (int i = 0; i < n; ++i){
  208.     //     for (int j = 0; j < m; ++j){
  209.     //         if (M[i][j] == '.') cout << ID[i][j] << " ";
  210.     //         else cout << "# ";
  211.     //     }
  212.     //     cout << endl;
  213.     // }
  214.  
  215.     // cout << G.n << endl;
  216.     // for (int i = 0; i < G.n; ++i)
  217.     //     cout << G.art[i] << " ";
  218.     // cout << endl;
  219.  
  220.     // for (int i = 0; i < G.n; ++i)
  221.     //     cout << G.id[i] << " ";
  222.     // cout << endl;
  223.  
  224.     // end debug
  225.  
  226.     vector<vector<bool>> mark(n, vector<bool>(m));
  227.     mark[A.first][A.second] = true;
  228.     queue<pii> foo; foo.push(A);
  229.  
  230.     while (!foo.empty()){
  231.         pii u = foo.front(); foo.pop();
  232.  
  233.         if (u == B)
  234.             break;
  235.  
  236.         for (int i = 0; i < 4; ++i){
  237.             int x = u.first + dx[i], y = u.second + dy[i];
  238.  
  239.             if (0 <= x && x < n && 0 <= y && y < m && !mark[x][y] && M[x][y] == '.'){
  240.                 mark[x][y] = true;
  241.                 foo.push(pii(x, y));
  242.             }
  243.         }
  244.     }
  245.  
  246.     pos_t start = {0, 0, -1};
  247.  
  248.     if (mark[B.first][B.second]){ // final position
  249.         for (int i = 0; i < 4; ++i){
  250.             int x = B.first + dx[i], y = B.second + dy[i];
  251.  
  252.             if (0 <= x && x < n && 0 <= y && y < m && mark[x][y]){
  253.                 start = {B.first, B.second, i};
  254.                 break;
  255.             }
  256.         }
  257.     }
  258.  
  259.     set<pii> final;
  260.     final.insert(B);
  261.  
  262.     if (start.k != -1){
  263.         // go everywhere
  264.  
  265.         queue<pos_t> q;
  266.         q.push(start);
  267.         vis[start.x][start.y][start.k] = true;
  268.  
  269.         while (!q.empty()){
  270.             auto cur = q.front(); q.pop();
  271.             int x = cur.x, y = cur.y, k = cur.k;
  272.  
  273.             // cout << x + 1 << " " << y + 1 << " " << k << endl;
  274.  
  275.             final.insert(pii(x, y));
  276.  
  277.             int nx = x + dx[k], ny = y + dy[k];
  278.             int nid = ID[nx][ny];
  279.  
  280.             for (int k = 0; k < 4; ++k){
  281.                 if (vis[x][y][k]) continue;
  282.  
  283.                 int fx = x + dx[k], fy = y + dy[k];
  284.  
  285.                 if (0 <= fx < n && 0 <= fy < m && M[fx][fy] == '.'){
  286.                     if (G.connected(nid, ID[fx][fy])){
  287.                         vis[x][y][k] = true;
  288.                         q.push({x, y, k});
  289.                     }
  290.                 }
  291.             }
  292.  
  293.             int bx = x - dx[k], by = y - dy[k];
  294.  
  295.             if (0 <= bx && bx < n && 0 <= by && by < m && M[bx][by] == '.' &&
  296.                 !vis[bx][by][k]){
  297.                 vis[bx][by][k] = true;
  298.                 q.push({bx, by, k});
  299.             }
  300.         }
  301.     }
  302.  
  303.     while (q-->0){
  304.         int x, y;
  305.         cin >> x >> y;
  306.         x--; y--;
  307.  
  308.         // cout << x + 1 << " " << y + 1 << " ";
  309.         cout << (final.find(pii(x,y)) == final.end() ? "NO" : "YES") << endl;
  310.     }
  311.  
  312.     return 0;
  313. }
Runtime error #stdin #stdout #stderr 0s 4304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/a6LMFi
language:
C++14 (clang 8.0)
created:
7 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!