Hướng dẫn giải của Bảo vệ nông trang

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -6
    hieubecclc01  đã bình luận lúc 4, Tháng 2, 2022, 13:19 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 13
    HV_DuongPhucThienNhan_BL_2022  đã bình luận lúc 28, Tháng 1, 2022, 15:32

    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;

    }


    • 3
      hieubecclc01  đã bình luận lúc 4, Tháng 2, 2022, 13:22 ← chỉnh sửa

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