a

a
 avatar
unknown
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