Advertisement
Guest User

Untitled

a guest
Sep 17th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.01 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement