Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cmath>
  5. #include <map>
  6. #include <algorithm>
  7. #include <string>
  8. #include <utility>
  9. #include <set>
  10. #include <stack>
  11. #include <deque>
  12. #include <ctime>
  13. #include <random>
  14. #include <cassert>
  15. #include <cmath>
  16. #include <climits>
  17. #include <queue>
  18. #include <cstring>
  19.  
  20. //#pragma GCC optimize ("O3")
  21.  
  22.  
  23.  
  24. #define fi(a,b) for (int i=a;i<b;i++)
  25. #define fj(a,b) for (int j=a;j<b;j++)
  26. #define fk(a,b) for (int k=a;k<b;k++)
  27. #define fi1(a,b) for (int i=a-1;i>=b;i--)
  28. #define fj1(a,b) for (int j=a-1;j>=b;j--)
  29. #define fx(x,a) for (auto& x : a)
  30.  
  31. #define lb lower_bound
  32. #define ub upper_bound
  33.  
  34. #define sz(x) (int)x.size()
  35. #define all(x) begin(x), end(x)
  36. #define rall(x) rbegin(x), rend(x)
  37.  
  38. struct pii {
  39. short first;
  40. short second;
  41. };
  42.  
  43. using namespace std;
  44. typedef long long ll;
  45. typedef char ch;
  46. typedef vector <int> vi;
  47. typedef vector<vector<int>> vvi;
  48. typedef vector<pii> vpii;
  49. typedef vector<vector<pii>> vvpii;
  50.  
  51.  
  52. const int MOD = 1000000007;
  53. const int INF = 1000000050;
  54. const int MX = 2001;
  55.  
  56. const double EPS = 1e-9;
  57.  
  58. mt19937 rnd;
  59.  
  60.  
  61. vpii order;
  62. char f[MX][MX];
  63. vpii g1[MX][MX];
  64. vpii gt[MX][MX];
  65. int col[MX][MX];
  66. vi col_sz;
  67. vvi gc;
  68.  
  69. void dfs(int i, int j, vector<vector<bool>> & used) {
  70. used[i][j] = 1;
  71. for (auto pos : g1[i][j]) {
  72. int ii = pos.first;
  73. int jj = pos.second;
  74. if (!used[ii][jj])
  75. dfs(ii, jj, used);
  76. }
  77. order.push_back({ short(i), short(j) });
  78. }
  79.  
  80. void dfs2(int i, int j, int cur) {
  81. col[i][j] = cur;
  82. ++col_sz[cur];
  83. fx(pos, gt[i][j]) {
  84. int ii = pos.first;
  85. int jj = pos.second;
  86. if (col[ii][jj] == -1)
  87. dfs2(ii, jj, cur);
  88. else {
  89. gc[col[ii][jj]].push_back(cur);
  90. }
  91. }
  92. }
  93.  
  94. void dfs3(int col, vector<bool> &used, vector<bool> &bad) {
  95. used[col] = 1;
  96. bad[col] = int(col_sz[col] > 1);
  97. fx(to, gc[col]) {
  98. if (!used[to])
  99. dfs3(to, used, bad);
  100. bad[col] = bad[col] | bad[to];
  101. }
  102. }
  103.  
  104. int main() {
  105. #ifdef LOCAL
  106. freopen("input.txt", "r", stdin);
  107. #endif
  108. ios_base::sync_with_stdio(false);
  109. cin.tie(NULL);
  110. cout.tie(NULL);
  111.  
  112. int n, m;
  113. cin >> n >> m;
  114. fi(0, n) {
  115. fj(0, m) {
  116. cin >> f[i][j];
  117. }
  118. }
  119.  
  120. fi(0, n) {
  121. int last = m - 1;
  122. fj1(m, 0) {
  123. if (f[i][j] != 'E') continue;
  124. fk(j + 1, last + 1)
  125. if (f[i][k] != '.') g1[i][j].push_back({ short(i), short(k) });
  126. last = j;
  127. }
  128. last = 0;
  129. fj(0, m) {
  130. if (f[i][j] != 'W') continue;
  131. fk(last, j)
  132. if (f[i][k] != '.') g1[i][j].push_back({ short(i), short(k) });
  133. last = j;
  134. }
  135. }
  136.  
  137. fj(0, m) {
  138. int last = n - 1;
  139. fi1(n, 0) {
  140. if (f[i][j] != 'S') continue;
  141. fk(i + 1, last + 1)
  142. if (f[k][j] != '.') g1[i][j].push_back({ short(k), short(j) });
  143. last = i;
  144. }
  145.  
  146. last = 0;
  147. fi(0, n) {
  148. if (f[i][j] != 'N') continue;
  149. fk(last, i)
  150. if (f[k][j] != '.') g1[i][j].push_back({ short(k), short(j) });
  151. last = i;
  152. }
  153. }
  154.  
  155. fi(0, n) {
  156. fj(0, m)
  157. g1[i][j].shrink_to_fit();
  158. }
  159.  
  160. vector<vector<bool>> used(n, vector<bool>(m, false));
  161. fi(0, n) {
  162. fj(0, m) {
  163. if (!used[i][j] && f[i][j] != '.') {
  164. dfs(i, j, used);
  165. }
  166. }
  167. }
  168. reverse(all(order));
  169.  
  170. fi(0, n) {
  171. fj(0, m) {
  172. for (auto pos : g1[i][j]) {
  173. int ii = pos.first;
  174. int jj = pos.second;
  175. gt[ii][jj].push_back({ short(i), short(j) });
  176. }
  177. }
  178. }
  179.  
  180. fi(0, n) {
  181. fj(0, m)
  182. gt[i][j].shrink_to_fit();
  183. }
  184.  
  185. fi(0, MX)
  186. fill(col[i], col[i] + MX, -1);
  187.  
  188. int cur = 0;
  189. fk(0, order.size()) {
  190. int i = order[k].first;
  191. int j = order[k].second;
  192. if (f[i][j] == '.') continue;
  193. if (col[i][j] == -1) {
  194. col_sz.push_back(0);
  195. gc.push_back({});
  196. dfs2(i, j, cur++);
  197. }
  198. }
  199.  
  200. fi(0, cur) {
  201. gc[i].shrink_to_fit();
  202. }
  203.  
  204. col_sz.shrink_to_fit();
  205. int ans = 0;
  206. vector<bool> bad(cur, 0);
  207. vector<bool> vis(cur, 0);
  208.  
  209. fi(0, cur) {
  210. if (!vis[i])
  211. dfs3(i, vis, bad);
  212. }
  213. fi(0, n) {
  214. fj(0, m) {
  215. if (f[i][j] != '.' && !bad[col[i][j]])
  216. ++ans;
  217. }
  218. }
  219. cout << ans;
  220. // you should actually read the stuff at the bottom
  221. }
  222.  
  223. /* stuff you should look for
  224. * int overflow, array bounds
  225. * special cases (n=1?), set tle
  226. * do smth instead of nothing and stay organized
  227. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement