Advertisement
a_chn

Untitled

Jan 25th, 2024
866
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.41 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.  
  30. int g[102][102];
  31. map<pair<int, int>, vector<pair<int, int> > > sw;
  32. bool vis[102][102];
  33. int n;
  34.  
  35. void ff(int x, int y){
  36.     if (vis[x][y] || g[x][y] == 0 || g[x][y] == -1) return;
  37.     vis[x][y] = true;
  38.     g[x][y] = 1;
  39.     for (auto i : sw[{x,y}]){
  40.         int a = i.f;
  41.         int b = i.s;
  42.         if (vis[a][b]) continue;
  43.         g[a][b] = 1;
  44.         if (vis[a - 1][b] == 1 || vis[a + 1][b] == 1 || vis[a][b + 1] == 1 || vis[a][b - 1] == 1) ff(a, b);
  45.     }
  46.     ff(x + 1, y);
  47.     ff(x - 1, y);
  48.     ff(x, y + 1);
  49.     ff(x, y - 1);
  50. }
  51. void solve(){
  52.     int m; cin >>n>>m;
  53.     for (int i = 0; i < m; i++){
  54.         int a,b,c,d; cin >> a>>b>>c>>d;
  55.         sw[{a,b}].push_back({c,d});
  56.     }
  57.     for (int i = 0; i < 102; i++){
  58.         for (int j = 0; j < 102; j++){
  59.             if (i == 0 || j == 0 || j == 101 || i == 101) g[i][j] = -1;
  60.             else g[i][j] = 0;
  61.             vis[i][j] = false;
  62.         }
  63.     }
  64.     g[1][1] = 1;
  65.     ff(1,1);
  66.     int ans = 0;
  67.     for (int i = 0; i <= n; i++){
  68.         for (int j = 0; j <= n; j++){
  69.             if (g[i][j] == 1) ans++;
  70.         }
  71.     }
  72.     cout << ans << nl;
  73. }
  74. // if you are unsure of how to do a problem by hand
  75. // the solution is most likely somewhat brute force (i.e binsearch)
  76. // if input is limited to 0-9 or a-z, usually you will loop through all combinations
  77. // of letters or numbers
  78. // constructive problems : start with 1 when constructing
  79. // :%y+ to copy all lines
  80. // rearrange math expressions
  81. // difference array? (a[i] - b[i])
  82. // debugging : reread the problem statement-every word is important!
  83. // debugging : print important variables!
  84. // think brute force sol first
  85. int main(){
  86.     ios::sync_with_stdio(false);
  87.     cin.tie(nullptr);
  88.     cout.tie(nullptr);
  89.     freopen("lightson.in", "r", stdin);
  90.     freopen("lightson.out", "w", stdout);
  91.     solve();
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement