## Editorial for Bảo vệ nông trang

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 1005

int h[N][N], n, m, qu[N*N];
bool vst[N][N];
int I[] = {-1,-1,-1,0,0,1,1,1}, J[] = {-1,0,1,-1,1,-1,0,1};

int hilltop( int i, int j ) {
int H = h[i][j], lo = 0, hi = 2;
vst[i][j] = 1; qu[0] = i; qu[1] = j;
int res = 1;
while(lo!=hi) {
int i = qu[lo++], j = qu[lo++];
rep(k,8) {
int x = i + I[k], y = j + J[k];
if( h[x][y] > H ) res = 0;
else if( h[x][y] == H && vst[x][y] == 0 ) {
vst[x][y] = 1;
qu[hi++] = x; qu[hi++] = y;
}
}
}
return res;
}

int main() {
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
#endif
scanf("%d%d",&n,&m);
fo(i,1,n) fo(j,1,m) scanf("%d",&h[i][j]);
rep(i,n+2) h[i][0] = h[i][m+1] = -1;
rep(j,m+2) h[0][j] = h[n+1][j] = -1;
int res = 0;
fo(i,1,n) fo(j,1,m)
if(!vst[i][j] && h[i][j] != 0) res += hilltop(i,j);
printf("%d\n", res);
return 0;
}


#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;
}


#### Code mẫu của RR

{
PROG: guardian
LANG: PASCAL
ID: invinci3
}
{\$R-,Q-}
const
FINP='';
FOUT='';
MAXN=701;
di:array[1..8] of longint=(-1,-1,-1,0,0,1,1,1);
dj:array[1..8] of longint=(-1,0,1,-1,1,-1,0,1);
var
h,xet:array[1..MAXN,1..MAXN] of longint;
qu,qv:array[1..MAXN*MAXN] of longint;
m,n,count,first,last:longint;
procedure inp; inline;
var
f:text;
i,j:longint;
begin
assign(f,FINP); reset(f);
for i:=1 to m do
begin
for j:=1 to n do read(f,h[i,j]);
end;
close(f);
end;
function check(u,v:longint):boolean; inline;
var
uu,vv,k:longint;
ok:boolean;
begin
first:=1; last:=1;
qu[1]:=u; qv[1]:=v; xet[u,v]:=1;
ok:=true;
while first<=last do
begin
u:=qu[first]; v:=qv[first]; inc(first);
for k:=1 to 8 do
begin
uu:=u+di[k]; vv:=v+dj[k];
if (uu>0) and (vv>0) and (uu<=m) and (vv<=n) then
begin
if h[uu,vv]>h[u,v] then ok:=false;
if (h[uu,vv]=h[u,v]) and (xet[uu,vv]=0) then
begin
inc(last); qu[last]:=uu; qv[last]:=vv;
xet[uu,vv]:=1;
end;
end;
end;
end;
check:=ok;
end;
procedure solve; inline;
var
i,j:longint;
begin
count:=0;
for i:=1 to m do
for j:=1 to n do
if xet[i,j]=0 then
if check(i,j) then inc(count);
end;
procedure ans; inline;
var
f:text;
begin
assign(f,FOUT); rewrite(f);
writeln(f,count);
close(f);
end;
begin
inp;
solve;
ans;
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int n,m,a[701][701],KQ=0;
bool free[701][701],d[701][701];

bool tm(int a,int b)
{
return (a>=1 && a<=n && b>=1 &&b<=m);
}

int DFS(int x,int y)
{
if(d[x][y] == false) return 0;
else if(!free[x][y]) return 1;
else
{
free[x][y]=false;
int K = 1;
for(int i = -1;i<=1;i++)
for(int j = -1;j<=1;j++)
if((i!=0 || j!=0) && tm(x+i,y+j) && a[x][y]==a[x+i][y+j]) K = K&DFS(x+i,y+j);
return K;
}
}

int main()
{
// freopen("NKGUARD.in","r",stdin);
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++)
{
scanf("%d",&a[i][j]);
free[i][j] = true;
d[i][j]=true;
}
for(int x = 1;x<=n;x++)
for(int y = 1;y<=m;y++)
for(int i = -1;i<=1;i++)
for(int j = -1;j<=1;j++)
{
if(i==0 &&j==0) continue;
else
{
if(tm(x+i,y+j) && a[x][y]<a[x+i][y+j])
d[x][y] = false;
}
}

for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++)
if(free[i][j])
{
KQ = KQ+DFS(i,j);
// printf("%d %d %d\n",i,j,KQ);
}
printf("%d",KQ);
// getch();
}


#### Code mẫu của ll931110

Program NKGUARD;
Type
rec = record
x,y: longint;
end;
Const
input  = '';
output = '';
Var
d: array[0..701,0..701] of longint;
a: array[0..701,0..701] of boolean;
dx,dy: array[1..8] of longint;
queue: array[1..50000] of rec;
n,m,count: longint;

Procedure init;
Var
f: text;
i,j: longint;
Begin
Assign(f, input);
Reset(f);

For i:= 1 to n do
For j:= 1 to m do read(f, d[i,j]);

Close(f);
Fillchar(a, sizeof(a), true);

For i:= 0 to n + 1 do
Begin
d[i,0]:= -1;
d[i,m + 1]:= -1;
End;

For i:= 0 to m + 1 do
Begin
d[0,i]:= -1;
d[n + 1,i]:= -1;
End;
End;

Procedure enter;
Begin
dx[1]:= -1;             dy[1]:= -1;
dx[2]:= -1;             dy[2]:= 0;
dx[3]:= -1;             dy[3]:= 1;
dx[4]:= 0;              dy[4]:= 1;
dx[5]:= 1;              dy[5]:= 1;
dx[6]:= 1;              dy[6]:= 0;
dx[7]:= 1;              dy[7]:= -1;
dx[8]:= 0;              dy[8]:= -1;
End;

Procedure BFS(p,q: longint);
Var
front,rear: longint;
u,v,i,j,k: longint;
top: boolean;
Begin
top:= true;

front:= 1;      rear:= 1;
queue[1].x:= p;         queue[1].y:= q;

Repeat
u:= queue[front].x;
v:= queue[front].y;
inc(front);
a[u,v]:= false;

For k:= 1 to 8 do
Begin
i:= u;
j:= v;

While d[i,j] = d[u,v] do
Begin
i:= i + dx[k];
j:= j + dy[k];

If (d[i,j] = d[u,v]) and a[i,j] then
Begin
inc(rear);
queue[rear].x:= i;
queue[rear].y:= j;
a[i,j]:= false;
End;
End;

If d[i,j] > d[u,v] then top:= false;
End;
Until front > rear;

If top then inc(count);
End;

Procedure solve;
Var
i,j: longint;
f: text;
Begin
count:= 0;
For i:= 1 to n do
For j:= 1 to m do if a[i,j] then BFS(i,j);

Assign(f, output);
Rewrite(f);
Writeln(f, count);
Close(f);
End;

Begin
init;
enter;
solve;
End.


#### Code mẫu của khuc_tuan

#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;
}


• commented on Feb. 4, 2022, 8:19 p.m. edited

.

• commented on Jan. 28, 2022, 10:32 p.m.

### include<iostream>

using namespace std;

const int MAX = 705;

int N,M; // Lần lượt là số lượng hàng, cột của ma trận int Answer; // Kết quả là số lượng đỉnh đồi int Map[MAX][MAX]; // Bản đồ của nông trang

bool Visit[MAX][MAX]; // Đánh dấu để kiểm tra đã duyệt hay chưa bool IsHill; // Đánh dấu xem có phải là đỉnh đồi hay không

int drow[8] = {-1,-1,-1, 0,0, 1,1,1}; int dcol[8] = {-1, 0, 1,-1,1,-1,0,1};

void DFS(int row, int col) { // Tại mỗi điểm ta sẽ đánh dấu điểm đó đã được duyệt Visit[row][col] = true;

for(int i = 0; i < 8; i++)
{
int r = row + drow[i];
int c = col + dcol[i];

if(r >= 0 && r < N && c >= 0 && c < M)
{
// Tại một điểm mà tồn tại 1 điểm kề có giá trị lớn hơn
// thì điểm đó không phải đỉnh đồi
if(IsHill && Map[r][c] > Map[row][col]) IsHill = false;

// Duyệt tới các điểm có cùng độ cao mà chưa được duyệt
// vì các điểm đó sẽ thuộc cùng 1 đỉnh đồi.
if(Map[r][c] == Map[row][col] && !Visit[r][c]) DFS(r, c);
}
}


}

int main() { //freopen("input.txt","r",stdin); ios::syncwithstdio(false);

// Nhập đầu vào
cin >> N >> M;
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
{
cin >> Map[i][j];
Visit[i][j] = false;
}

// Duyệt từng phần tử trong ma trận
// và kiểm tra tại phần tử chưa được xét
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
if(!Visit[i][j])
{
// Khởi tạo IsHill = true, sau đó sử dụng thuật toán DFS
// để duyệt ma trận. Sau quá trình duyệt, nếu như IsHill vẫn có
// giá trị true thì chứng tỏ điểm vừa xét là đỉnh đồi.
IsHill = true;
DFS(i, j);