- #include#include#include#include#include#include#include#include#include < set > #include#include using namespace std;#define lowbit(x)((x) & ( - x))#define pi acos( - 1.0)#define eps 1e-9#define MOD 12345678#define INF 1000000000#define mem(a, b) memset(a, b, sizeof(a))#define FOR(i, a, n) for (int i = a; i <= n; ++i)#define FO(i, a, n) for (int i = a; ii)#define bug puts("H");#define lch p << 1,
- l,
- mid#define rch p << 1 | 1,
- mid + 1,
- r#define mp make_pair#define pb push_back typedef pair < int,
- int > PII;
- typedef vector < int > VI;#pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL;
- int Scan() {
- int res = 0,
- flag = 0;
- char ch;
- if ((ch = getchar()) == ' - ') flag = 1;
- else if (ch >= '0' && ch <= '9') res = ch - '0';
- while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0');
- return flag ? -res: res;
- }
- void Out(int a) {
- if (a < 0) {
- putchar(' - ');
- a = -a;
- }
- if (a >= 10) Out(a / 10);
- putchar(a % 10 + '0');
- }
- const int N = 2005;
- //Code begin...
- struct Edge {
- int p,
- next,
- w;
- }
- edge[650005];
- int head[805],
- cnt = 2,
- s,
- t,
- vis[805];
- char s1[25][25],
- s2[25][25];
- queue < int > Q;
- void add_edge(int u, int v, int w) {
- edge[cnt].p = v;
- edge[cnt].next = head[u];
- edge[cnt].w = w;
- head[u] = cnt++;
- edge[cnt].p = u;
- edge[cnt].next = head[v];
- edge[cnt].w = 0;
- head[v] = cnt++;
- }
- int bfs(void) {
- int i,
- v;
- mem(vis, -1);
- while (!Q.empty()) Q.pop();
- vis[s] = 0;
- Q.push(s);
- while (!Q.empty()) {
- v = Q.front();
- Q.pop();
- for (i = head[v]; i; i = edge[i].next) {
- if (edge[i].w > 0 && vis[edge[i].p] == -1) {
- vis[edge[i].p] = vis[v] + 1;
- Q.push(edge[i].p);
- }
- }
- }
- return vis[t] != -1;
- }
- int dfs(int x, int low) {
- int i,
- a,
- temp = low;
- if (x == t) return low;
- for (i = head[x]; i; i = edge[i].next) {
- if (edge[i].w > 0 && vis[edge[i].p] == vis[x] + 1) {
- a = dfs(edge[i].p, min(edge[i].w, temp));
- temp -= a;
- edge[i].w -= a;
- edge[i ^ 1].w += a;
- if (temp == 0) break;
- }
- }
- if (temp == low) vis[x] = -1;
- return low - temp;
- }
- int main() {
- int n,
- m,
- d,
- sum = 0;
- scanf("%d%d%d", &n, &m, &d);
- FO(i, 0, n) scanf("%s", s1[i] + 1);
- FO(i, 0, n) scanf("%s", s2[i] + 1);
- s = 0,
- t = 2 * n * m + 1;
- FO(i, 0, n) FOR(j, 1, m) {
- if (s1[i][j] != '0') add_edge(i * m + j, i * m + j + n * m, s1[i][j] - '0');
- if (s2[i][j] == 'L') add_edge(s, i * m + j, 1),
- ++sum;
- if (i1 - i) 1) <= d) add_edge(i * m + j + n * m, t, INF);
- FO(k, 0, n) FOR(l, 1, m) {
- if (k == i && l == j) continue;
- if (abs(k - i) + abs(l - j) <= d) add_edge(i * m + j + n * m, k * m + l, INF);
- }
- }
- int res = 0,
- temp;
- while (bfs()) while (temp = dfs(s, INF)) res += temp;
- printf("%d\n", sum - res);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1968871.html