Advertisement
a_chn

Untitled

Jan 25th, 2024
834
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.70 KB | None | 0 0
  1. #include <algorithm>
  2. #include <array>
  3. #include <bitset>
  4. #include <cassert>
  5. #include <chrono>
  6. #include <climits>
  7. #include <cmath>
  8. #include <complex>
  9. #include <cstring>
  10. #include <functional>
  11. #include <iomanip>
  12. #include <iostream>
  13. #include <map>
  14. #include <numeric>
  15. #include <queue>
  16. #include <random>
  17. #include <set>
  18. #include <vector>
  19. using namespace std;
  20.  
  21. #define ll long long
  22. #define forn(i, s, n) for (int i = s; i < n; i++)
  23. #define bforn(i, s) for (int i = s; i >= 0; i--)
  24. // for pairs
  25. #define s second
  26. #define f first
  27. const int M = 2e5 + 1;
  28. const char nl = '\n';
  29. const int E = 1505;
  30.  
  31. int g[E][E];
  32. bool blocked;
  33.  
  34. void ff(int i, int j){
  35.     if(i < 0 || i >= E || j < 0 || j >= E) return;
  36.     if (g[i][j] == 1 || g[i][j] == 2) return;
  37.     if (g[i][j] == -1){
  38.         blocked = false;
  39.         return;
  40.     }
  41.     g[i][j] = 2;
  42.     ff(i + 1, j);
  43.     ff(i - 1, j);
  44.     ff(i, j - 1);
  45.     ff(i, j + 1);
  46. }
  47.  
  48. void solve(){
  49.     int n; cin >> n;
  50.     string s; cin >> s;
  51.     for (int i = 0; i < E; i++){
  52.         for (int j = 0; j < E; j++){
  53.             if (i == 0 || i == E || j == 0 || j == E) g[i][j] = -1;
  54.             else g[i][j] = 0;
  55.         }
  56.     }
  57.     int i = 1000, j = 1000;
  58.     g[i][j] = 1;
  59.     for (int k = 0; k < s.size(); k++){
  60.         g[i][j] = 1;
  61.         if (s[k] == 'N'){
  62.             g[i + 1][j] = 1;
  63.             g[i + 2][j] = 1;
  64.             i+=2;
  65.         }
  66.         if (s[k] == 'W'){
  67.             g[i][j - 1] = 1;
  68.             g[i][j - 2] = 1;
  69.             j -= 2;
  70.         }
  71.         if (s[k] == 'E'){
  72.             g[i][j + 1] = 1;
  73.             g[i][j + 2] = 1;
  74.             j+=2;
  75.         }
  76.         if (s[k] == 'S'){
  77.             g[i - 1][j] = 1;
  78.             g[i - 2][j] = 1;
  79.             i -= 2;
  80.         }
  81.     }
  82.     int ans = 0;
  83.     for (int k = 0; k < E; k++){
  84.         for (int l = 0; l < E; l++){
  85.             if (g[k][l] != 0) continue;
  86.             blocked = true;
  87.             ff(k, l);
  88.             if (blocked) ans++;
  89.         }
  90.     }
  91.     cout << ans << nl;
  92. }
  93. // if you are unsure of how to do a problem by hand
  94. // the solution is most likely somewhat brute force (i.e binsearch)
  95. // if input is limited to 0-9 or a-z, usually you will loop through all combinations
  96. // of letters or numbers
  97. // constructive problems : start with 1 when constructing
  98. // :%y+ to copy all lines
  99. // rearrange math expressions
  100. // difference array? (a[i] - b[i])
  101. // debugging : reread the problem statement-every word is important!
  102. // debugging : print important variables!
  103. // think brute force sol first
  104. int main(){
  105.     ios::sync_with_stdio(false);
  106.     cin.tie(nullptr);
  107.     cout.tie(nullptr);
  108.     freopen("gates.in", "r", stdin);
  109.     freopen("gates.out", "w", stdout);
  110.     solve();
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement