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';
- int g[102][102];
- map<pair<int, int>, vector<pair<int, int> > > sw;
- bool vis[102][102];
- int n;
- void ff(int x, int y){
- if (vis[x][y] || g[x][y] == 0 || g[x][y] == -1) return;
- vis[x][y] = true;
- g[x][y] = 1;
- for (auto i : sw[{x,y}]){
- int a = i.f;
- int b = i.s;
- if (vis[a][b]) continue;
- g[a][b] = 1;
- if (vis[a - 1][b] == 1 || vis[a + 1][b] == 1 || vis[a][b + 1] == 1 || vis[a][b - 1] == 1) ff(a, b);
- }
- ff(x + 1, y);
- ff(x - 1, y);
- ff(x, y + 1);
- ff(x, y - 1);
- }
- void solve(){
- int m; cin >>n>>m;
- for (int i = 0; i < m; i++){
- int a,b,c,d; cin >> a>>b>>c>>d;
- sw[{a,b}].push_back({c,d});
- }
- for (int i = 0; i < 102; i++){
- for (int j = 0; j < 102; j++){
- if (i == 0 || j == 0 || j == 101 || i == 101) g[i][j] = -1;
- else g[i][j] = 0;
- vis[i][j] = false;
- }
- }
- g[1][1] = 1;
- ff(1,1);
- int ans = 0;
- for (int i = 0; i <= n; i++){
- for (int j = 0; j <= n; j++){
- if (g[i][j] == 1) 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("lightson.in", "r", stdin);
- freopen("lightson.out", "w", stdout);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement