a
aunknown
c_cpp
5 months ago
2.1 kB
1
Indexable
#include <bits/stdc++.h> using namespace std; #define nl '\n' #define fi first #define se second #define MASK(x) (1LL << (x)) #define BIT(mask, x) (((mask) >> (x)) & 1LL) #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define FOD(i, b, a) for(int i = (b); i >= (a); i--) typedef long long ll; typedef pair < int , int > pii; typedef pair < ll , ll > pll; typedef pair < int , pii > piii; template <class A, class B> bool maximize(A& x, B y) { if (x < y) return x = y, true; else return false;} template <class A, class B> bool minimize(A& x, B y) { if (x > y) return x = y, true; else return false;} const int N = 1e6 + 7; const int MOD = 1e9 + 7; const int INF = 1e9; int dx[] = {-1,-1,-1,0,0,1,1,1}; int dy[] = {-1,0,1,-1,1,-1,0,1}; int n, m, ans = 0; int check[1000][1000], a[1000][1000]; bool inside(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } void bfs(int X, int Y) { queue < pii > q; int cnt = 1; q.push({X, Y}); check[X][Y] = 1; while (!q.empty()) { int u = q.front().fi; int v = q.front().se; q.pop(); FOR(i, 0, 7) { int x = u + dx[i]; int y = v + dy[i]; if (inside(x, y)) { if (a[x][y] == a[u][v] && !check[x][y]) { check[x][y] = 1; q.push({x, y}); } else if (a[x][y] > a[u][v]) { cnt = 0; } } } } ans += cnt; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define task "a" if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin >> n >> m; FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j]; FOR(i, 1, n) FOR(j, 1, m) if (!check[i][j]) bfs(i, j); cout << ans; return 0; } /* 1. Think Greedy 2. Think Brute Force 3. Think Solution in reverse order 4. Think DP 5. Check base cases for DP and prove solution for Greedy 6. Think Graph */
Editor is loading...
Leave a Comment