Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <array>
- #include <bitset>
- #include <cassert>
- #include <chrono>
- #include <climits>
- #include <cmath>
- #include <complex>
- #include <cstring>
- #include <functional>
- #include <iomanip>
- #include <iostream>
- #include <map>
- #include <numeric>
- #include <queue>
- #include <random>
- #include <set>
- #include <vector>
- using namespace std;
- #define ll long long
- #define forn(i, s, n) for (int i = s; i < n; i++)
- #define bforn(i, s) for (int i = s; i >= 0; i--)
- // for pairs
- #define s second
- #define f first
- const int M = 2e5 + 1;
- const char nl = '\n';
- const int E = 1505;
- int g[E][E];
- bool blocked;
- void ff(int i, int j){
- if(i < 0 || i >= E || j < 0 || j >= E) return;
- if (g[i][j] == 1 || g[i][j] == 2) return;
- if (g[i][j] == -1){
- blocked = false;
- return;
- }
- g[i][j] = 2;
- ff(i + 1, j);
- ff(i - 1, j);
- ff(i, j - 1);
- ff(i, j + 1);
- }
- void solve(){
- int n; cin >> n;
- string s; cin >> s;
- for (int i = 0; i < E; i++){
- for (int j = 0; j < E; j++){
- if (i == 0 || i == E || j == 0 || j == E) g[i][j] = -1;
- else g[i][j] = 0;
- }
- }
- int i = 1000, j = 1000;
- g[i][j] = 1;
- for (int k = 0; k < s.size(); k++){
- g[i][j] = 1;
- if (s[k] == 'N'){
- g[i + 1][j] = 1;
- g[i + 2][j] = 1;
- i+=2;
- }
- if (s[k] == 'W'){
- g[i][j - 1] = 1;
- g[i][j - 2] = 1;
- j -= 2;
- }
- if (s[k] == 'E'){
- g[i][j + 1] = 1;
- g[i][j + 2] = 1;
- j+=2;
- }
- if (s[k] == 'S'){
- g[i - 1][j] = 1;
- g[i - 2][j] = 1;
- i -= 2;
- }
- }
- int ans = 0;
- for (int k = 0; k < E; k++){
- for (int l = 0; l < E; l++){
- if (g[k][l] != 0) continue;
- blocked = true;
- ff(k, l);
- if (blocked) ans++;
- }
- }
- cout << ans << nl;
- }
- // if you are unsure of how to do a problem by hand
- // the solution is most likely somewhat brute force (i.e binsearch)
- // if input is limited to 0-9 or a-z, usually you will loop through all combinations
- // of letters or numbers
- // constructive problems : start with 1 when constructing
- // :%y+ to copy all lines
- // rearrange math expressions
- // difference array? (a[i] - b[i])
- // debugging : reread the problem statement-every word is important!
- // debugging : print important variables!
- // think brute force sol first
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- freopen("gates.in", "r", stdin);
- freopen("gates.out", "w", stdout);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement