首先我们可以二分一个答案时间T，这样就将最优性问题
转化为了判定性问题。下面我们考虑对于已知的T的判定
对于矩阵中所有的空点bfs一次，得出来每个点到门的距离，
然后连接空点和每个能在t时间内到达的门一条边，容量为1，
之后连接源和每个空点一条边，容量为1，门连接汇边，容量为t。
判断最大流是否满流就好了。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
type
rec =record
x, y :longint;
end;
var
n, m :longint;
pre, other, len, time :array[..] of longint;
last :array[..] of longint;
l :longint;
que1 :array[..] of rec;
dis :array[..,..] of longint;
go :array[..,..] of longint;
num :array[..,..] of longint;
source, sink :longint;
sum :longint;
map :array[..,..] of char;
que, d :array[..] of longint;
function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end;
procedure connect(a,b,c,d:longint);
begin
inc(l);
pre[l]:=last[a];
last[a]:=l;
other[l]:=b;
len[l]:=c;
time[l]:=d;
end;
procedure make(a,b:longint);
var
h, t, curx, cury, nx, ny :longint;
i, j :longint;
f :boolean;
begin
connect(source,num[a,b],,);
connect(num[a,b],source,,);
fillchar(dis,sizeof(dis),);
dis[a,b]:=; que1[].x:=a; que1[].y:=b;
h:=; t:=;
while h<t do
begin
inc(h);
curx:=que1[h].x; cury:=que1[h].y;
for i:= to do
begin
nx:=curx+go[,i]; ny:=cury+go[,i];
if (nx<) or (nx>n) or (ny<) or (ny>m) then continue;
if dis[nx,ny]<> then continue;
if map[nx,ny]='X' then continue;
inc(t);
que1[t].x:=nx; que1[t].y:=ny;
dis[nx,ny]:=dis[curx,cury]+;
end;
end;
f:=false;
for i:= to n do
for j:= to m do
if map[i,j]='D' then
if dis[i,j]<> then
begin
f:=true;
connect(num[a,b],num[i,j],,dis[i,j]-);
connect(num[i,j],num[a,b],,dis[i,j]-);
end;
if not f then
begin
writeln('impossible');
halt;
end;
end;
procedure init;
var
i, j :longint;
begin
go[,]:=-; go[,]:=; go[,]:=; go[,]:=-;
readln(n,m);
for i:= to n do
begin
for j:= to m do read(map[i,j]);
readln;
end;
for i:= to n do
for j:= to m do num[i,j]:=(i-)*m+j;
source:=*n*m+; sink:=source+;
l:=;
for i:= to n do
for j:= to m do
if map[i,j]='.' then
begin
make(i,j);
inc(sum);
end;
for i:= to n do
for j:= to m do
if map[i,j]='D' then
begin
connect(num[i,j],sink,,);
connect(sink,num[i,j],,);
end;
end;
function bfs(up:longint):boolean;
var
q, p :longint;
h, t, cur :longint;
begin
fillchar(d,sizeof(d),);
que[]:=source; h:=; t:=;
d[source]:=;
while h<t do
begin
inc(h);
cur:=que[h];
q:=last[cur];
while q<> do
begin
if (len[q]>) and (time[q]<=up) then
begin
p:=other[q];
if (d[p]=) then
begin
inc(t);
que[t]:=p;
d[p]:=d[cur]+;
if p=sink then exit(true);
end;
end;
q:=pre[q];
end;
end;
exit(false);
end;
function dinic(x,flow,up:longint):longint;
var
tmp, rest :longint;
q, p :longint;
begin
rest:=flow;
if x=sink then exit(flow);
q:=last[x];
while q<> do
begin
p:=other[q];
if (len[q]>) and (time[q]<=up) and (rest>) and (d[x]=d[p]-) then
begin
tmp:=dinic(p,min(len[q],rest),up);
dec(rest,tmp);
dec(len[q],tmp);
inc(len[q xor ],tmp);
end;
q:=pre[q];
end;
exit(flow-rest);
end;
function judge(mid:longint):boolean;
var
q :longint;
tot :longint;
i :longint;
begin
q:=last[sink];
while q<> do
begin
len[q]:=;
len[q xor ]:=mid;
q:=pre[q];
end;
tot:=;
while bfs(mid) do
tot:=tot+dinic(source,maxlongint,mid);
for i:= to l do if i mod = then
begin
inc(len[i],len[i xor ]);
len[i xor ]:=;
end;
if tot<sum then exit(false) else exit(true);
end;
procedure main;
var
l, r, mid, ans :longint;
begin
l:=; r:=;
while l<=r do
begin
mid:=(l+r) div ;
if judge(mid) then
begin
ans:=mid;
r:=mid-;
end else l:=mid+;
end;
writeln(ans);
end;
begin
init;
main;
end.