虽然我知道大家都能过,那是因为数据很水。
数组其实需要开较大,不然按照对门的点按时间拆点的网络流做法会在做以下这种数据时溢出。
20 20
DDDDDDDDDDDDDDDDDDDD
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
D..................D
DDDDDDDDDDDDDDDDDDDD
这题数据还有其他非常水的地方,比如说如果你预处理 SPFA 求门到人的最短距离时,门对门建边也能过,但实际上到了一个门是不能选择走相邻的门出去的,bzoj 有这样的数据可以卡这种情况,比如说以下这种:
5 4
XDXX
DXXX
D..X
X..X
XXXX
如果你都选择走第三行第一个点的门走,那必须要时间 4,如果你在后面人走的时候选择不走下面的门而走上面一个其实可以做到 3,但是这是不合法的。
如果你不判断一下
if(tx<1||ty<1||tx>n||ty>m||maze[tx][ty]!='.')
//连向的 tx,ty 只能是 '.' 点
continue;
你的程序会出 3。
综上,数据确实很水,即使 AC 也应该要注意以上几点,管理员当然也可以酌情增强数据qwq。