BZOJ 1102: [POI 2007] 산봉우리 와 계곡 Grz Flood Fill 알고리즘

Description
FGD 어린 이 는 등산 을 특히 좋아해 서 등산 할 때 산봉우리 와 산 골 짜 기 를 연구 하고 있 었 다.그 는 그의 여정 에 대해 계획 을 세 울 수 있 도록 산봉우리 와 계곡 의 수 를 알 고 싶 어 했다.지 도 를 지정 합 니 다. FGD 가 여행 하고 싶 은 지역 입 니 다. 지 도 는 n * n 의 격자 로 나 뉘 어 있 고 각 칸 (i, j) 의 높이 w (i, j) 는 주어진 것 입 니 다.만약 두 칸 에 공공 정점 이 있다 면, 그들 은 바로 인접 한 칸 이다.(그래서 (i, j) 와 인접 한 칸 은 (i? 1, j? 1), (i? 1, j), (i? 1, j + 1), (i, j? 1), (i, j + 1), (i + 1, j? 1), (i + 1, j), (i + 1, j), (i + 1, j + 1) 가 있다.우 리 는 하나의 칸 의 집합 S 를 산봉우리 (계곡) 로 정의 하고 1. S 의 모든 칸 은 같은 높이 를 가지 고 있다.2. S 의 모든 칸 이 연 결 됩 니 다. 3. s 는 S 에 속 하고 s 와 인접 한 s' 는 S 에 속 하지 않 습 니 다.모두 ws (산봉우리) 나 ws (계곡) 가 있다.주어진 지도 에 대해 산봉우리 와 계곡 의 수 를 구 하 는 것 이 임무 입 니 다. 모든 칸 이 같은 높이 라면 지도 전체 가 산봉우리 이자 계곡 입 니 다.Input
첫 번 째 줄 에는 지도 크기 (1 < = n < = 1000) 를 나타 내 는 정수 n 이 포함 되 어 있 습 니 다.다음 n * n 의 행렬 은 지도 상의 각 칸 의 높이 를 나타 낸다.(0<=w<=1000000000) Output
산봉우리 와 계곡 의 수 를 나타 내 는 두 가지 수 를 포함해 야 한다.Sample Input 입력 샘플 1
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
입력 샘플 2
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7 샘플 출력 출력 샘플 1
2 1
출력 샘플 2
3 3
문제 풀이 방법: 누 드 Flood Fill 알고리즘 의 응용.하지만 이 문 제 는 DFS 로 스 택 이 터 지기 때문에 BFS 로 고 쳐 써 야 한다.
코드 는 다음 과 같 습 니 다:

#include 
using namespace std;
const int maxn = 1010;
#define pii pair
#define MP(x, y) make_pair(x, y)
int n, ans1, ans2, a[maxn][maxn];
bool flag, vis[maxn][maxn];
const int dir[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void Floodfill(int x, int y)
{
    vis[x][y] = 1;
    queue  que;
    que.push(MP(x, y));
    while(!que.empty()){
        pii now = que.front(); que.pop();
        for(int i = 0; i < 8; i++){
            int dx = now.first + dir[i][0];
            int dy = now.second + dir[i][1];
            if(dx <= 0 || dx > n || dy <= 0 || dy > n) continue;
            if(a[dx][dy] > a[now.first][now.second]) flag = 0;
            if(a[dx][dy] == a[now.first][now.second] && !vis[dx][dy]){
                vis[dx][dy] = 1;
                que.push(MP(dx, dy));
            }
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(!vis[i][j]){
                flag = 1;
                Floodfill(i, j);
                ans1 += flag;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = -a[i][j];
        }
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(!vis[i][j]){
                flag = 1;
                Floodfill(i, j);
                ans2 += flag;
            }
        }
    }
    printf("%d %d
", ans1, ans2);
    return 0;
}