NKGUARD - Bảo vệ nông trang
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <cstdio>
#include <cstring>
using namespace std;
int dx[] = {-1,0,0,1,-1,1,-1,1};
int dy[] = {0,-1,1,0,-1,-1,1,1};
int m, n;
int a[707][707];
bool mark[707][707], vs[707][707];
void dfs(int i, int j) {
if(vs[i][j]) return;
vs[i][j] = true;
for(int h=0;h<8;++h) {
int x = i + dx[h];
int y = j + dy[h];
if(x>=0 && x<m && y>=0 && y<n && a[x][y]==a[i][j]) dfs(x,y);
}
}
void dfs2(int i, int j) {
if(mark[i][j]) return;
mark[i][j] = true;
for(int h=0;h<8;++h) {
int x = i + dx[h];
int y = j + dy[h];
if(x>=0 && x<m && y>=0 && y<n && !vs[x][y]) dfs2(x,y);
}
}
int main() {
scanf("%d%d", &m, &n);
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
scanf("%d", &a[i][j]);
for(int i=0;i<m;++i)
for(int j=0;j<n;++j) {
for(int h=0;h<8;++h) {
int x = i + dx[h];
int y = j + dy[h];
if(x>=0 && x<m && y>=0 && y<n && a[x][y]>a[i][j])
mark[i][j] = true;
}
}
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(mark[i][j] && !vs[i][j]) dfs(i,j);
int result = 0;
memset( mark, false, sizeof(mark));
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(!vs[i][j] && !mark[i][j]) {
++result;
dfs2(i,j);
}
printf("%d\n", result);
return 0;
}