没有将门进行拆点，而是将门向时间连边，点集就是汇源点+人+门+二分的时间，但是wa了最后三个点，不知道哪错了qwq

#include<bits/stdc++.h>
using LL = long long;

constexpr int INF = 0x3f3f3f3f;
template< typename T >
struct Edge {
    int from, to;
    T cap, flow;

    Edge(int u, int v, T c, T f) : from(u), to(v), cap(c), flow(f) {}
};
template< typename T >
struct Dinic {
    int n, m;
    int Source, Sink;
    std::vector< Edge< T > > edges;
    std::vector< std::vector< int > > G;
    std::vector< int > d, cur;
    std::vector< bool > vis;

    // number of vertices
    Dinic(int n) : n(n), d(n), cur(n), vis(n), G(n) {}
    
    void AddEdge(int from, int to, T cap) {
        edges.push_back(Edge< T >(from, to, cap, 0));
        edges.push_back(Edge< T >(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BFS() {
        vis.assign(n, 0);
        std::queue< int > Q;
        Q.push(Source);
        d[Sink] = 0;
        vis[Source] = true;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); ++ i) {
                Edge< T > &e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[Sink];
    }

    T DFS(int x, T a) {
        if (x == Sink || a == 0) {
            return a;
        }
        T flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); ++ i) {
            Edge< T > &e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, std::min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) {
                    break;
                }
            }
        }
        return flow;
    }

    T Maxflow(int s, int t) {
        this->Source = s;
        this->Sink = t;
        T flow = 0;
        while (BFS()) {
            cur.assign(n, 0);
            flow += DFS(Source, INF);
        }
        return flow;
    }
};
struct Node {
    int x, y, step;
};
struct Point {
    int x, y;
};
const int N = 25;
int n, m, dis[N][N][N][N];
char s[N][N];
std::vector< Point > start, end;
bool vis[N][N];
std::vector< std::pair< int, int > > go {
    {1, 0}, {-1, 0},
    {0, 1}, {0, -1}
};
int BFS(int x1, int y1, int x2, int y2) {
    memset(vis, false, sizeof vis);
    vis[x1][y1] = true;
    std::queue< Node > q;
    q.push({x1, y1, 0});
    while (!q.empty()) {
        Node p = q.front();
        q.pop();
        if (p.x == x2 && p.y == y2) {
            return p.step;
        }
        for (auto &[i, j] : go) {
            int nx = p.x + i, ny = p.y + j;
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]) {
                vis[nx][ny] = true;
                q.push({nx, ny, p.step + 1});
            } 
        }
    }
    return INF;
}
bool check(int mid) {
    int x = start.size(), y = end.size();
    Dinic< int > F(x + y + mid + 2);
    int s = x + y + mid, t = s + 1;
    for (int i = 0; i < x; ++ i) {
        F.AddEdge(s, i, 1);
    }
    for (int i = 0; i < mid; ++ i) {
        F.AddEdge(x + y + i, t, INF);
    }
    for (int i = 0; i < y; ++ i) {
        for (int j = 0; j < mid; ++ j) {
            F.AddEdge(x + i, x + y + j, 1);
        }
    }
    for (int i = 0; i < x; ++ i) {
        for (int j = 0; j < y; ++ j) {
            if (dis[start[i].x][start[i].y][end[j].x][end[j].y] <= mid) {
                F.AddEdge(i, x + j, 1);
            }
        }
    }
    return F.Maxflow(s, t) == x;
}
signed main() {
    #ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
    #endif

    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++ i) {
        scanf("%s", s[i]);
        for (int j = 0; j < m; ++ j) {
            if (s[i][j] == '.') {
                start.push_back({i, j});
            } else if (s[i][j] == 'D') {
                end.push_back({i, j});
            }
        }
    }
    for (auto &[x1, y1] : start) {
        for (auto &[x2, y2] : end) {
            dis[x1][y1][x2][y2] = BFS(x1, y1, x2, y2);
        }
    }
    int l = 1, r = 1000, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    if (ans != -1) {
        printf("%d\n", ans);
    } else {
        puts("impossible");
    }
    return 0;
}