Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <cmath>
- #include <map>
- #include <algorithm>
- #include <string>
- #include <utility>
- #include <set>
- #include <stack>
- #include <deque>
- #include <ctime>
- #include <random>
- #include <cassert>
- #include <cmath>
- #include <climits>
- #include <queue>
- #include <cstring>
- //#pragma GCC optimize ("O3")
- #define fi(a,b) for (int i=a;i<b;i++)
- #define fj(a,b) for (int j=a;j<b;j++)
- #define fk(a,b) for (int k=a;k<b;k++)
- #define fi1(a,b) for (int i=a-1;i>=b;i--)
- #define fj1(a,b) for (int j=a-1;j>=b;j--)
- #define fx(x,a) for (auto& x : a)
- #define lb lower_bound
- #define ub upper_bound
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- struct pii {
- short first;
- short second;
- };
- using namespace std;
- typedef long long ll;
- typedef char ch;
- typedef vector <int> vi;
- typedef vector<vector<int>> vvi;
- typedef vector<pii> vpii;
- typedef vector<vector<pii>> vvpii;
- const int MOD = 1000000007;
- const int INF = 1000000050;
- const int MX = 2001;
- const double EPS = 1e-9;
- mt19937 rnd;
- vpii order;
- char f[MX][MX];
- vpii g1[MX][MX];
- vpii gt[MX][MX];
- int col[MX][MX];
- vi col_sz;
- vvi gc;
- void dfs(int i, int j, vector<vector<bool>> & used) {
- used[i][j] = 1;
- for (auto pos : g1[i][j]) {
- int ii = pos.first;
- int jj = pos.second;
- if (!used[ii][jj])
- dfs(ii, jj, used);
- }
- order.push_back({ short(i), short(j) });
- }
- void dfs2(int i, int j, int cur) {
- col[i][j] = cur;
- ++col_sz[cur];
- fx(pos, gt[i][j]) {
- int ii = pos.first;
- int jj = pos.second;
- if (col[ii][jj] == -1)
- dfs2(ii, jj, cur);
- else {
- gc[col[ii][jj]].push_back(cur);
- }
- }
- }
- void dfs3(int col, vector<bool> &used, vector<bool> &bad) {
- used[col] = 1;
- bad[col] = int(col_sz[col] > 1);
- fx(to, gc[col]) {
- if (!used[to])
- dfs3(to, used, bad);
- bad[col] = bad[col] | bad[to];
- }
- }
- int main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- int n, m;
- cin >> n >> m;
- fi(0, n) {
- fj(0, m) {
- cin >> f[i][j];
- }
- }
- fi(0, n) {
- int last = m - 1;
- fj1(m, 0) {
- if (f[i][j] != 'E') continue;
- fk(j + 1, last + 1)
- if (f[i][k] != '.') g1[i][j].push_back({ short(i), short(k) });
- last = j;
- }
- last = 0;
- fj(0, m) {
- if (f[i][j] != 'W') continue;
- fk(last, j)
- if (f[i][k] != '.') g1[i][j].push_back({ short(i), short(k) });
- last = j;
- }
- }
- fj(0, m) {
- int last = n - 1;
- fi1(n, 0) {
- if (f[i][j] != 'S') continue;
- fk(i + 1, last + 1)
- if (f[k][j] != '.') g1[i][j].push_back({ short(k), short(j) });
- last = i;
- }
- last = 0;
- fi(0, n) {
- if (f[i][j] != 'N') continue;
- fk(last, i)
- if (f[k][j] != '.') g1[i][j].push_back({ short(k), short(j) });
- last = i;
- }
- }
- fi(0, n) {
- fj(0, m)
- g1[i][j].shrink_to_fit();
- }
- vector<vector<bool>> used(n, vector<bool>(m, false));
- fi(0, n) {
- fj(0, m) {
- if (!used[i][j] && f[i][j] != '.') {
- dfs(i, j, used);
- }
- }
- }
- reverse(all(order));
- fi(0, n) {
- fj(0, m) {
- for (auto pos : g1[i][j]) {
- int ii = pos.first;
- int jj = pos.second;
- gt[ii][jj].push_back({ short(i), short(j) });
- }
- }
- }
- fi(0, n) {
- fj(0, m)
- gt[i][j].shrink_to_fit();
- }
- fi(0, MX)
- fill(col[i], col[i] + MX, -1);
- int cur = 0;
- fk(0, order.size()) {
- int i = order[k].first;
- int j = order[k].second;
- if (f[i][j] == '.') continue;
- if (col[i][j] == -1) {
- col_sz.push_back(0);
- gc.push_back({});
- dfs2(i, j, cur++);
- }
- }
- fi(0, cur) {
- gc[i].shrink_to_fit();
- }
- col_sz.shrink_to_fit();
- int ans = 0;
- vector<bool> bad(cur, 0);
- vector<bool> vis(cur, 0);
- fi(0, cur) {
- if (!vis[i])
- dfs3(i, vis, bad);
- }
- fi(0, n) {
- fj(0, m) {
- if (f[i][j] != '.' && !bad[col[i][j]])
- ++ans;
- }
- }
- cout << ans;
- // you should actually read the stuff at the bottom
- }
- /* stuff you should look for
- * int overflow, array bounds
- * special cases (n=1?), set tle
- * do smth instead of nothing and stay organized
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement