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

Code mẫu của ladpro98

#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);
  readln(f,m,n);
  for i:=1 to m do
    begin
      for j:=1 to n do read(f,h[i,j]);
      readln(f);
    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);

                Readln(f, n, m);
                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;
}

Comments

Please read the guidelines before commenting.

-7

hieubecclc01 commented on Feb. 4, 2022, 1:19 p.m. ← edited →

.

This comment is hidden due to too much negative feedback. Show it anyway.

HV_DuongPhucThienNhan_BL_2022 commented on Jan. 28, 2022, 3: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);
            if(IsHill) Answer++;
        }

// In kết quả số đỉnh đồi
cout << Answer << endl;

return 0;

}

5

hieubecclc01 commented on Feb. 4, 2022, 1:22 p.m. ← edited →

cảm ơn bạn nhiều nha