티스토리 뷰

알고리즘 관련/BOJ

BOJ)4627 뛰어라 도마뱀

JASON 자손9319 2017. 1. 6. 15:55

문제: icpc.me/4627


도마뱀이 맨해튼 거리가 D이하인 거리를 이동 할 수 있을 때 탈출을 하지 못하는 도마뱀의 수를 정하면 된다.


문제를 잘 읽어보면 같은 시간에는 최대 하나의 도마뱀만 기둥에 서 있을 수 있고 기둥에는 최대 도약 횟수가 정해져 있다.


이를 이용하여 그래프를 모델링을 하면 


소스->도마뱀들의 처음 위치


각 방-> 맨하탄 거리가 D이내인 방


외각->Destination


으로 모델링을 할 수 있다. 이 때 우리는 최대 도약 횟수를 생각해야 하므로 정점들을 분할하여 정점을 분할하는 간선의 가중치를 최대 도약횟수로 주고 최대유량을 구해주면 원하는 답을 얻을 수 있다.


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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#define INF 987654321
#define S 1251
#define E 1252
using namespace std;
int t, n, m, d, res;
int arr[25][25];
string a;
char b;
int work[1255];
int level[1255];
struct Edge {
    int v, cap, rev;
    Edge(int v, int cap, int rev) :v(v), cap(cap), rev(rev) {}
};
vector<vector<Edge>> vt;
void addEdge(int s, int e, int c) {
    vt[s].emplace_back(e, c, vt[e].size());
    vt[e].emplace_back(s, 0, vt[s].size() - 1);
}
bool bfs() {
    memset(level, -1sizeof(level));
    queue<int> qu;
    qu.push(S);
    level[S] = 0;
    while (qu.size()) {
        int here = qu.front();
        qu.pop();
        for (auto i : vt[here]) {
            int there = i.v;
            int cap = i.cap;
            if (level[there] == -&& cap > 0) {
                level[there] = level[here] + 1;
                qu.push(there);
            }
        }
    }
    return level[E] != -1;
}
int dfs(int here, int crtcap) {
    if (here == E)return crtcap;
    for (int &= work[here]; i < vt[here].size(); i++) {
        int there = vt[here][i].v;
        int cap = vt[here][i].cap;
        if (level[here] + == level[there] && cap>0) {
            int df = dfs(there, min(cap, crtcap));
            if (df > 0) {
                vt[here][i].cap -= df;
                vt[there][vt[here][i].rev].cap += df;
                return df;
            }
        }
    }
    return 0;
}
void chk(int x, int y) {
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            if (abs(x - i) + abs(y - j) <= d)
                addEdge(x*(m + 2+ y + 625, i*(m + 2+ j, INF);
        }
    }
}
int main() {
    scanf("%d"&t);
    for (int tt = 1; tt <= t; tt++) {
        scanf("%d%d"&n, &d);
        res = 0;
        vt.clear();
        vt.resize(1255);
        for (int i = 1; i <= n; i++) {
            cin >> a;
            if (i == 1)
                m = a.length();
            for (int j = 0; j < m; j++)
                arr[i][j + 1= a[j] - '0';
        }
        for (int i = 1; i <= n; i++) {
            getchar();
            for (int j = 1; j <= m; j++) {
                scanf("%c"&b);
                if (b == 'L') {
                    addEdge(S, i*(m + 2+ j, 1);
                    res++;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                chk(i, j);
            }
        }
        for (int i = 0; i <= n + 1; i++) {
            for (int j = 0; j <= m + 1; j++) {
                if (i == || i == n + || j == || j == m + 1) {
                    addEdge(i*(m + 2+ j, i*(m + 2+ j + 625, INF);
                    addEdge(i*(m + 2+ j + 625, E, INF);
                }
                else
                    addEdge(i*(m + 2+ j, i*(m + 2+ j + 625, arr[i][j]);
            }
        }
        while (bfs()) {
            memset(work, 0sizeof(work));
            while (1) {
                int flow = dfs(S, INF);
                if (!flow)break;
                res -= flow;
            }
        }
        if (res >= 2)
            printf("Case #%d: %d lizards were left behind.\n", tt, res);
        else if (res == 1)
            printf("Case #%d: %d lizard was left behind.\n", tt, res);
        else
            printf("Case #%d: no lizard was left behind.\n", tt);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2042 구간 합 구하기  (0) 2017.01.10
BOJ)1654 랜선 자르기  (0) 2017.01.06
BOJ)4627 뛰어라 도마뱀  (0) 2017.01.06
BOJ)13701 중복 제거  (0) 2017.01.06
BOJ)1647 도시 분할 계획  (0) 2017.01.06
BOJ)4948 베르트랑 공준  (0) 2017.01.06
댓글
댓글쓰기 폼