Algoogle

Algorithm for Programming Contest

PKU 3620 Avoid The Lakes

Category: PKU Tag: dfs

Avoid The Lakes

問題概要


解法


連結している個数をそれぞれdfsで数える.

コード


(3620.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <cstdio>

using namespace std;

int h, w, K;
bool rect[128][128];
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};

inline bool in(int x, int y){ return x >= 0 && x < w && y >= 0 && y < h;}

int dfs(int x, int y){
    rect[x][y] = 0;
    int ret = 1;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(in(nx, ny) && rect[nx][ny]) ret += dfs(nx, ny);
    }
    return ret;
}

int main(){
    scanf("%d%d%d", &w, &h, &K);
    for(int i = 0; i < K; i++){
        int x, y; scanf("%d%d", &x, &y);
        rect[x-1][y-1] = 1;
    }
    int ans = 0;
    for(int x = 0; x < w; x++)
        for(int y = 0; y < h; y++)
            if(rect[x][y]) ans = max(ans, dfs(x, y));
    printf("%d\n", ans);
    return 0;
}

Comments