[BZOJ] 1619: [Usaco 2008 Nov] 농장 을 지 키 는 목장 (dfs)

http://www.lydsy.com/JudgeOnline/problem.php?id=1619
우선 어 쩔 수 없 이 제목 을 못 알 아 봤 어 요...
원래 떨 어 진 연결 블록 을 찾 는 거 야...
정렬 후 dfs 표 시 를 하면 됩 니 다.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



const int N=705, dx[]={1,1,1,0,0,-1,-1,-1}, dy[]={1,0,-1,1,-1,1,0,-1};  

int vis[N][N], h[N][N], ans, cnt, n, m;

struct dat{ int x, y, h; } mp[N*N];

bool cmp(const dat &a, const dat &b) { return a.h>b.h; }

void dfs(int x, int y) {

	vis[x][y]=1;

	rep(i, 8) {

		int fx=dx[i]+x, fy=dy[i]+y;

		if(fx<1 || fy<1 || fx>n || fy>m || vis[fx][fy] || h[fx][fy]>h[x][y]) continue;

		dfs(fx, fy);

	}

}

int main() {

	read(n); read(m);

	for1(i, 1, n) for1(j, 1, m) read(h[i][j]), mp[++cnt].h=h[i][j], mp[cnt].x=i, mp[cnt].y=j;

	sort(mp+1, mp+1+cnt, cmp);

	for1(i, 1, cnt) {

		int x=mp[i].x, y=mp[i].y;

		if(!vis[x][y]) { dfs(x, y); ++ans; }

	}

	print(ans);

	return 0;

}

 
 
 
 
Description
The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows. He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map. A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.
 
농부 JOHN 의 농부 에는 작은 언덕 이 많 았 다. 그 는 그곳 에 경호원 (...) 을 배치 해서 그의 꽤 값 나 가 는 젖소 들 을 지 키 려 고 했다.그 는 작은 언덕 에 경호원 한 명 을 배치 하면 총 몇 명의 경호원 을 모집 해 야 하 는 지 알 고 싶 어 했다.그 는 지금 수중 에 디지털 행렬 로 지형 을 표시 하 는 지 도 를 가지 고 있다.이 행렬 은 N 행 (1 < N < = 100) 과 M 열 (1 < M < = 70) 이 있 습 니 다. 행렬 의 모든 요 소 는 H ij (0 < = H ij < = 10, 000) 값 으로 이 지역 의 해발 고 도 를 나 타 냅 니 다. 그 에 게 지도 상에 몇 개의 작은 언덕 이 있 는 지 통계 해 주세요.(또는 지도의 경계 와 인접 해 있다)이 요소 와 그 주변 에 있 는 모든 요소 의 집합 을 작은 언덕 이 라 고 합 니 다. 여기 서 인접 한 의 미 는 한 요소 가 다른 가로 좌표 와 세로 좌표 의 차이 가 1 을 초과 하지 않 으 면 이 두 요소 가 인접 하 다 는 것 입 니 다. 문제 의 이름: guard 입력 형식: 첫 번 째 줄: 빈 칸 으로 구 분 된 정수 N 과 M 두 번 째 줄 에서 N + 1 줄 까지 입 니 다.: I + 1 줄 은 지도 에 있 는 I 줄 을 설명 합 니 다. M 개의 빈 칸 으로 구 분 된 정수 가 있 습 니 다. H ij. 입력 사례:: 3 출력 사례 설명: 지도 에 세 개의 작은 언덕 이 있 습 니 다. 모든 작은 언덕 의 산봉우리 위 치 는 각각 왼쪽 상단 (높이 는 4), 오른쪽 상단 (높이 는 1) 과 아래쪽 (높이 는 2) 입 니 다.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij
Output
* Line 1: A single integer that specifies the number of hilltops
Sample Input
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
Sample Output
3
HINT
   세 개의 언덕 은 왼쪽 상단 의 높이 가 4 인 격자, 오른쪽 상단 의 높이 가 1 인 격자, 그리고 마지막 줄 의 높이 가 2 인 격자 이다.
Source
Silver