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.
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
This comment is hidden due to too much negative feedback. Show it anyway.
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;
}
int main() { //freopen("input.txt","r",stdin); ios::syncwithstdio(false);
}
cảm ơn bạn nhiều nha