网络流板子，应该没有问题，最后一个点应为 $0$，输出 $1$。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 800 + 10, inf = 1e5;

template <class T>
struct FlowGragh {
    int s, t, size, etot;
    int head[N], cur[N], dis[N];
    struct edge {
        int v, nxt;
        T w;
    } e[N * N];

    void init(int _s, int _t, int n) {
        s = _s, t = _t, size = n;
        etot = 0;
        fill(head, head + 1 + size, -1);
    }

    inline void add(int u, int v, T w) {
        e[etot] = {v, head[u], w}; head[u] = etot++;
        e[etot] = {u, head[v], 0}; head[v] = etot++;
    }

    bool bfs() {
        for (int i = 0; i <= size; i++) {
            dis[i] = 0;
            cur[i] = head[i];
        }
        queue<int> q;
        q.push(s); dis[s] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt) {
                int v = e[i].v;
                if (e[i].w && !dis[v]) {
                    dis[v] = dis[u] + 1;
                    if (v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, T m) {
        if (u == t) return m;
        ll flow = 0;
        for (int &i = cur[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if (e[i].w && dis[v] == dis[u] + 1) {
                T f = dfs(v, min(m, e[i].w));
                e[i].w -= f;
                e[i ^ 1].w += f;
                m -= f;
                flow += f;
                if (!m) break;
            }
        }
        if (!flow) dis[u] = -1;
        return flow;
    }

    T dinic() {
        T res = 0;
        bfs();
        while (bfs()) res += dfs(s, inf);
        return res;
    }
};
FlowGragh<int> g;
int n, m, d;
int a[N][N];

bool check(int x, int y, int xx, int yy) {
    if (x == xx && y == yy) return false;
    return (x - xx) * 1ll * (x - xx)
         + (y - yy) * 1ll * (y - yy) <= d;
}

int main() {
    scanf("%d%d%d", &n, &m, &d);
    int s = 2 * n * m + 1;
    int t = 2 * n * m + 2;
    g.init(s, t, t);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%1d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (!a[i][j]) continue;
            int id = (i - 1) * m + j;
            int _id = id + n * m;
            g.add(id, _id, a[i][j]);
            for (int ii = 1; ii <= n; ii++)
                for (int jj = 1; jj <= m; jj++) {
                    if (!a[ii][jj]) continue;
                    int to = (ii - 1) * m + jj;
                    if (check(i, j, ii, jj))
                        g.add(_id, to, inf);
            }
            if (n - i < d || i <= d || m - j < d || j <= d)
                g.add(_id, t, inf);
    }
    int tot = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int id = (i - 1) * m + j;
            char c;
            scanf(" %c", &c);
            if (c == 'L') {
                g.add(s, id, 1);
                tot++;
            }
    }
    printf("%d\n", tot - g.dinic());
    return 0;
}