Description
在一个 \(r\) 行 \(c\) 列的网格地图中有一些高度不同的石柱, 一些石柱上站着一些蜥蜴, 你的任务是让尽量多的蜥蜴逃到边界外. 每行每列中相邻石柱的距离为 \(1\), 蜥蜴的跳跃距离是 \(d\), 即蜥蜴可以跳到平面距离不超过 \(d\) 的任何一个石柱上. 石柱都不稳定, 每次当蜥蜴跳跃时, 所离开的石柱高度减 \(1\) (如果仍然落在地图内部, 则到达的石柱高度不变), 如果该石柱原来高度为 \(1\), 则蜥蜴离开后消失. 以后其他蜥蜴不能落脚. 任何时刻不能有两只蜥蜴在同一个石柱上.
Input
输入第一行为三个整数 \(r, c, d\), 即地图的规模与最大跳跃距离.
以下 \(r\) 行为石竹的初始状态,\(0\) 表示没有石柱,\(1-3\) 表示石柱的初始高度.
以下 \(r\) 行为蜥蜴位置,"L" 表示蜥蜴,"." 表示没有蜥蜴.
Output
输出仅一行, 包含一个整数, 即无法逃离的蜥蜴总数的最小值.
Sample Input
5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........Sample Output
1Data Range
100% 的数据满足:\(1 \leq r, c \leq 20, 1 \leq d \leq 4\)
Explanation
此题用网络流过掉, 但是还是拆点, 而且是经典的把一个几何点拆成两个拓扑点. 比如一个 点负责流入, 另一个流出; 流入和流出之间一定有一个限制流量即允许从该处跳出的青蛙数量. 进一步地, 可以从一个流出连到另一个流入, 即青蛙的移动法则.
大概瞎搞一发 Dinic 可以水过......
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
#define rep(_var,_begin,_end) for (int _var=_begin;_var<=_end;_var++)
#define sqr(__x) ((__x)*(__x))
using namespace std;
typedef long long lli;
const int maxN = 100, maxn = 10100, maxm = 500100;
const int infinit = 0x0f7f7f7f;
class Dinic
{
public:
struct edge
{
int u, v, flow;
edge *next, *rev;
};
int n, s, t, ecnt;
edge *edges[maxn], epool[maxm];
int level[maxn];
void add_edge(int u, int v, int flow)
{
// printf("%d %d %d\n", u, v, flow);
edge *p = &epool[++ecnt],
*q = &epool[++ecnt];
p->u = u; p->v = v; p->flow = flow;
p->next = edges[u]; edges[u] = p; p->rev = q;
q->u = v; q->v = u; q->flow = 0;
q->next = edges[v]; edges[v] = q; q->rev = p;
return ;
}
bool make_level(void)
{
memset(level, 0, sizeof(level));
queue<int> que;
que.push(s);
level[s] = 1;
while (!que.empty()) {
int p = que.front();
que.pop();
for (edge *ep = edges[p]; ep; ep = ep->next)
if (ep->flow && !level[ep->v]) {
level[ep->v] = level[p] + 1;
que.push(ep->v);
}
}
if (level[t] > 0)
return true;
return false;
}
int dfs(int p, int mn)
{
if (p == t)
return mn;
int sum = 0, tmp;
for (edge *ep = edges[p]; ep && sum < mn; ep = ep->next)
if (ep->flow && level[ep->v] == level[p] + 1) {
tmp = dfs(ep->v, min(mn - sum, ep->flow));
if (tmp > 0) {
sum += tmp;
ep->flow -= tmp;
ep->rev->flow += tmp;
}
}
return sum;
}
int eval(void)
{
int sum = 0, tmp;
while (make_level()) {
tmp = dfs(s, infinit);
if (tmp <= 0)
break;
sum += tmp;
}
return sum;
}
} graph;
int read_number(void) { char ch = '\0';
while (ch < '0' || ch > '9') ch = getchar();
return ch - '0'; }
bool read_position(void) { char ch = '\0';
while (ch != '.' && ch != 'L') ch = getchar();
return ch == 'L'; }
int r, c, d;
int arr[maxN][maxN];
#define get_pos(__y,__x) (((__y)-1)*c+(__x))
bool judge_node_pair(int x1, int y1, int x2, int y2)
{
// if (x1 < 1 || x1 > c || x2 < 1 || x2 > c) return false;
// if (y1 < 1 || y1 > r || y2 < 1 || y2 > r) return false;
if (x1 == x2 && y1 == y2) return false;
if (!arr[x1][y1] || !arr[x2][y2]) return false;
return sqr(x1 - x2) + sqr(y1 - y2) <= sqr(d);
}
int main(int argc, char **argv)
{
scanf("%d%d%d", &r, &c, &d);
graph.n = r * c * 2 + 2;
graph.s = 0;
graph.t = 801;
int tot_cnt = 0; // All lizards
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
arr[i][j] = read_number();
// Linking from source to entries
rep(i, 1, r) rep(j, 1, c)
if (read_position()) {
graph.add_edge(graph.s, get_pos(i,j), 1);
tot_cnt++;
}
// Building exit portals to sink
rep(i, 1, d) rep(j, d+1, r-d) {
graph.add_edge(get_pos(j,i) + 400, graph.t, infinit);
graph.add_edge(get_pos(j,c-i+1) + 400, graph.t, infinit);
}
rep(i, 1, d) rep(j, 1, c) {
graph.add_edge(get_pos(i,j) + 400, graph.t, infinit);
graph.add_edge(get_pos(r-i+1,j) + 400, graph.t, infinit);
}
// Building edges between nodes
rep(x1, 1, r) rep(y1, 1, c) rep(x2, x1-d, x1+d) rep(y2, y1-d, y1+d)
if (judge_node_pair(x1, y1, x2, y2))
graph.add_edge(get_pos(x1,y1) + 400, get_pos(x2,y2), infinit);
// Building flow limit in a single node
rep(i, 1, r) rep(j, 1, c)
if (arr[i][j])
graph.add_edge(get_pos(i,j), get_pos(i,j) + 400, arr[i][j]);
// Executing maximum flow
int res = graph.eval();
printf("%d\n", tot_cnt - res);
return 0;
}