Prison Break

admin

Problem Description
Rompire is a robot kingdom and a lot of robots live there peacefully. But one day, the king of Rompire was captured by human beings. His thinking circuit was changed by human and thus became a tyrant. All those who are against him were put into jail, including our clever Micheal#1. Now it’s time to escape, but Micheal#1 needs an optimal plan and he contacts you, one of his human friends, for help.
The jail area is a rectangle contains n×m little grids, each grid might be one of the following:
1) Empty area, represented by a capital letter ‘S’.
2) The starting position of Micheal#1, represented by a capital letter ‘F’.
3) Energy pool, represented by a capital letter ‘G’. When entering an energy pool, Micheal#1 can use it to charge his battery ONLY ONCE. After the charging, Micheal#1’s battery will become FULL and the energy pool will become an empty area. Of course, passing an energy pool without using it is allowed.
4) Laser sensor, represented by a capital letter ‘D’. Since it is extremely sensitive, Micheal#1 cannot step into a grid with a laser sensor.
5) Power switch, represented by a capital letter ‘Y’. Once Micheal#1 steps into a grid with a Power switch, he will certainly turn it off.

In order to escape from the jail, Micheal#1 need to turn off all the power switches to stop the electric web on the roof—then he can just fly away. Moving to an adjacent grid (directly up, down, left or right) will cost 1 unit of energy and only moving operation costs energy. Of course, Micheal#1 cannot move when his battery contains no energy.

The larger the battery is, the more energy it can save. But larger battery means more weight and higher probability of being found by the weight sensor. So Micheal#1 needs to make his battery as small as possible, and still large enough to hold all energy he need. Assuming that the size of the battery equals to maximum units of energy that can be saved in the battery, and Micheal#1 is fully charged at the beginning, Please tell him the minimum size of the battery needed for his Prison break.


Input
Input contains multiple test cases, ended by 0 0. For each test case, the first line contains two integer numbers n and m showing the size of the jail. Next n lines consist of m capital letters each, which stands for the description of the jail.You can assume that 1<=n,m<=15, and the sum of energy pools and power switches is less than 15.


Output
For each test case, output one integer in a line, representing the minimum size of the battery Micheal#1 needs. If Micheal#1 can’t escape, output -1.


Sample Input
5 5
GDDSS
SSSFS
SYGYS
SGSYS
SSYSS
0 0


Sample Output
4


Source
2010 Asia Hangzhou Regional Contest

admin

【题目大意】机器人从F出发，走到G可以充电，走到Y关掉开关，D不能走进，要求把所有开关关掉，且电量最少，并求出该最小电量。

【题目解析】机器人从出发点出发要求走过所有的Y，因为点很少，所以就能想到经典的TSP问题（起初我也想到了），但关于G点（不要YY）能充电的问题不知道怎么办，看了下解题报告才知道。G点可以充电，到达G点就把当前能量更新为电池容量然后继续走。因为每个G点只能充一次电，这就好像TSP中的每个点只能走一次一样（G和Y都可以走多次，但走到G充电后，该点就变为了S，而走到Y关上开关以后，Y也变成了S。这是一个很巧妙地想法，所以要求Y点只能关一次开关，G点只能充一次电，这就是TSP了。Orz赛场上可以秒杀这题的大神们），然后就是二分答案了，用状压DP判定当前电池容量的情况下是否能符合条件。

【状态表示】dp[s][i]表示到达当前i点状态为s时最大的剩余的能量

【转移方程】同TSP问题了

【边界条件】dp[1<<sid][sid] = rongliang.即出发点的能量就是电池容量