maksyuki 发表于 oj 分类,标签: ,

Instantaneous Transference

It was long ago when we played the game Red Alert. There is a magic function for the game objects which is called instantaneous transfer. When an object uses this magic function, it will be transferred to the specified point immediately, regardless of how far it is.

Now there is a mining area, and you are driving an ore-miner truck. Your mission is to take the maximum ores in the field.

The ore area is a rectangle region which is composed by n × m small squares, some of the squares have numbers of ores, while some do not. The ores can't be regenerated after taken.

The starting position of the ore-miner truck is the northwest corner of the field. It must move to the eastern or southern adjacent square, while it can not move to the northern or western adjacent square. And some squares have magic power that can instantaneously transfer the truck to a certain square specified. However, as the captain of the ore-miner truck, you can decide whether to use this magic power or to stay still. One magic power square will never lose its magic power; you can use the magic power whenever you get there.


The first line of the input is an integer T which indicates the number of test cases.

For each of the test case, the first will be two integers NM (2 ≤ NM ≤ 40).

The next N lines will describe the map of the mine field. Each of the N lines will be a string that contains M characters. Each character will be an integer X (0 ≤ X ≤ 9) or a '*' or a '#'. The integer X indicates that square has X units of ores, which your truck could get them all. The '*' indicates this square has a magic power which can transfer truck within an instant. The '#' indicates this square is full of rock and the truck can't move on this square. You can assume that the starting position of the truck will never be a '#' square.

As the map indicates, there are K '*' on the map. Then there follows K lines after the map. The next K lines describe the specified target coordinates for the squares with '*', in the order from north to south then west to east. (the original point is the northwest corner, the coordinate is formatted as north-south, west-east, all from 0 to N - 1,- 1).


For each test case output the maximum units of ores you can take.

Sample Input


2 2



0 0

Sample Output



South Central China 2008 hosted by NUDT



算法分析:每个非”#”点和左边、下边的点之间连一条有向边,若遇到”#”点则不连,当然需要将平面图的坐标重新映射一下。对于每个魔法点”*”,需要额外判断是否能够向其目标点连有向边(目标点非”#”才能连)。易知同一个强连通分量中的点可以双向可达,所以可以缩点,用其中所有点的val值的和来表示缩点后的点的点权,缩点后的图是一个有向无环图且没有重边,所以可以看做是树。使用dp[i]表示以i为根的子树所具有的最大价值。dp[i]初始化成对应缩点后的点权。状态转移方程为dp[u] = max (dp[u], vval[u] + dp[v]),vval[u]表示u点处的点权(缩点后)且v是u的子节点。最后输出顶点1所在缩点处的dp值即可