SHARE
TWEET

Untitled

a guest Sep 17th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Codeforces 1214D - Treasure Island
  2. // Lúcio Cardoso
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int, int> pii;
  9.  
  10. const int maxn = 1e6+10;
  11.  
  12. int n, m;
  13.  
  14. vector<pair<int, char>> tab[maxn];
  15.  
  16. int tt;
  17. int in[maxn], low[maxn];
  18.  
  19. bool reach[maxn];
  20.  
  21. vector<int> grafo[maxn], dag[maxn];
  22.  
  23. bool tem;
  24.  
  25. int linha[] = {1, 0};
  26. int coluna[] = {0, 1};
  27.  
  28. void dfs0(int u)
  29. {
  30.     reach[u] = 1;
  31.     for (auto v: dag[u])
  32.         if (!reach[v])
  33.             dfs0(v);
  34. }
  35.  
  36. bool dfs(int u, int p)
  37. {
  38.     in[u] = low[u] = ++tt;
  39.  
  40.     bool ja = 0;
  41.  
  42.     for (auto v: grafo[u])
  43.     {
  44.         if (in[v])
  45.         {
  46.             if (v != p)
  47.                 low[u] = min(low[u], in[v]);
  48.  
  49.             continue;
  50.         }
  51.  
  52.         bool ja2 = dfs(v, u);
  53.         ja |= ja2;
  54.  
  55.         if (ja2)
  56.         {
  57.             if (u != 1 && u != n*m)
  58.             {
  59.                 if (low[v] >= in[u])
  60.                     tem = 1;
  61.             }
  62.         }
  63.  
  64.         low[u] = min(low[u], low[v]);
  65.     }
  66.  
  67.     if (u == n*m) ja = 1;
  68.     return ja;
  69. }
  70.  
  71. int main(void)
  72. {
  73.     scanf("%d %d", &n, &m);
  74.  
  75.     int qtd = 0;
  76.  
  77.     for (int i = 1; i <= n; i++)
  78.     {
  79.         for (int j = 1; j <= m; j++)
  80.         {
  81.             char c;
  82.             scanf(" %c", &c);
  83.             tab[i].push_back({++qtd, c});
  84.         }
  85.     }
  86.  
  87.     for (int i = 1; i <= n; i++)
  88.     {
  89.         for (int j = 1; j <= m; j++)
  90.         {
  91.             if (tab[i][j-1].second == '#') continue;
  92.  
  93.             int u = tab[i][j-1].first;
  94.  
  95.             for (int k = 0; k < 2; k++)
  96.             {
  97.                 int a = i+linha[k], b = j+coluna[k];
  98.                 if (a < 1 || a > n || b < 1 || b > m) continue;
  99.  
  100.                 if (tab[a][b-1].second != '#')
  101.                     dag[u].push_back(tab[a][b-1].first);
  102.             }
  103.         }
  104.     }
  105.  
  106.     dfs0(1);
  107.  
  108.     for (int i = 1; i <= n; i++)
  109.     {
  110.         for (int j = 1; j <= m; j++)
  111.         {
  112.             if (tab[i][j-1].second == '#') continue;
  113.  
  114.             int u = tab[i][j-1].first;
  115.  
  116.             for (int k = 0; k < 2; k++)
  117.             {
  118.                 int a = i+linha[k], b = j+coluna[k];
  119.                 if (a < 1 || a > n || b < 1 || b > m) continue;
  120.  
  121.                 if (tab[a][b-1].second != '#' && reach[tab[a][b-1].first])
  122.                 {
  123.                     grafo[u].push_back(tab[a][b-1].first);
  124.                     grafo[tab[a][b-1].first].push_back(u);
  125.                 }
  126.             }
  127.         }
  128.     }
  129.  
  130.     dfs(1, 0);
  131.  
  132.     if (!in[n*m])
  133.     {
  134.         printf("0\n");
  135.         return 0;
  136.     }
  137.  
  138.     if (grafo[1].size() == 1)
  139.     {
  140.         printf("1\n");
  141.         return 0;
  142.     }
  143.  
  144.     if (tem)
  145.         printf("1\n");
  146.     else
  147.         printf("2\n");
  148. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top