二分问题

二分问题

捉老鼠

Description

我来到一个n×m(n,m<=10)的迷宫中。
迷宫里有空地，也有石头。
空地用”.”表示，石头用”#”表示，而我所在的位置用”L”表示。
每一单位时间，我可以向上、下、左、右四个方向移动一个单位，也可以停在原地。
空地里有一些时刻会出现老鼠，假如在那一个时刻，我恰好呆在那个格子里，我就可以抓到那一只老鼠。
我最多可以抓到多少只老鼠？

Input

第一行n和m，以后n行，每行m个字符，表示迷宫。
然后一个整数p(p≤30000)，代表老鼠个数。
以后p行，每行3个数，分别是老鼠的坐标和老鼠出现的时刻（时刻在2^31-1以内）。
初始时刻为0。

Output

一个整数，代表最多能捉到的老鼠个数。

Sample Input

5 5
L....
..#..
###.#
#....
#.###
4
2 2 2
2 1 3
5 2 13
5 1 14

Sample Output

3

HINT

本题的坐标，是以迷宫的右上角为（1，1），最上面一行从右往左第二个为（2，1）。
数据范围见题面。

Solution

预处理将所有老鼠按照出现时间排序，并用BFS求出所有点对之间的最短距离dist[ x1,y1,x2,y2 $x_1,y_1,x_2,y_2$]。
假设排序后第i只老鼠的坐标为(x[i],y[i])，出现的时间为time[i]。
如果用f[i]表示前i只老鼠中，第i只一定要捉，最多能捉到几只老鼠，容易得到以下的状态转移方程：
f[i]=max{f[j]+1}(j=1…i−1,time[j]+d[i,j]≤time[i]) $f[i]=max\{f[j]+1\}(j=1…i-1,time[j]+d[i,j]≤time[i])$
其中d[i,j]表示第i只老鼠坐标到第j只老鼠坐标的距离值。这个算法的时间复杂度为 O(p2) $O(p^2)$，对于p≤30000的范围来说略大了一些。
这个算法是否存在优化的余地呢？
经过仔细分析，我们发现每一个状态f[i]的决策数目为 O(p) $O(p)$级别。
而如果我们从格子的角度考虑，总共只有