NKGUARD - Bảo vệ nông trang

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 777;
using namespace std;
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int a[N][N];
bool was[N][N];
bool high[N * N];
ii Q[N * N];
int m, n, res;

void BFS(int xx, int yy) {
    int l = 1, r = 1, i, x, y;
    ii u;
    Q[1] = ii(xx, yy); was[xx][yy] = true;
    while (l <= r) {
        u = Q[l++];
        for(i=0; i<8; i++) {
            x = u.X + dx[i]; y = u.Y + dy[i];
            if (x < 0 || y < 0 || x > m || y > n) continue;
            if (!was[x][y] && a[x][y] == a[xx][yy]) {
                Q[++r] = ii(x, y); was[x][y] = true;
            }
            else
                if (a[xx][yy] < a[x][y]) high[res] = false;
        }
    }
}

int main()
{
    scanf("%d %d\n", &m, &n);
    int i, j, cnt = 0;
    for(i=1; i<=m; i++) for(j=1; j<=n; j++) scanf("%d", &a[i][j]);
    for(i=1; i<=m; i++) for(j=1; j<=n; j++) if (!was[i][j]) {
        res++; high[res] = true; BFS(i, j);
    }
    for(i=1; i<=res; i++) if (high[i]) cnt++;
    printf("%d", cnt);
    return 0;
}

Download