# Bee

问题描述 :

QQ’s forest is represented by a square grid of N by N unit cells, whose sides are parallel to the north-south and east-west directions. Each cell is occupied by a tree, by a patch of grass, by a hive or by QQ’s home. Two cells are considered adjacent if one of them is immediately to the north, south, east or west of the other (but not on a diagonal). QQ is a clumsy bear, so every time he makes a step, it has to be to an adjacent cell. QQ can only walk on grass and cannot go through trees or hives, and he can make at most S steps per minute.

At the moment when the bee alarm is sounded, QQ is in the grassy cell containing the honeypot, and the bees are in every cell containing a hive (there may be more than one hive in the forest). During each minute from this time onwards, the following events happen in the following order:

1. If QQ is still eating honey, he decides whether to keep eating or to leave. If he continues eating, he does not move for the whole minute. Otherwise, he leaves immediately and takes up to S steps through the forest as described above. QQ cannot take any of the honey with him, so once he has moved he cannot eat honey again.

2. After QQ is done eating or moving for the whole minute, the bees spread one unit further across the grid, moving only into the grassy cells. Specifically, the swarm of bees spreads into every grassy cell that is adjacent to any cell already containing bees. Furthermore, once a cell contains bees it will always contain bees (that is, the swarm does not move, but it grows).

In other words, the bees spread as follows: When the bee alarm is sounded, the bees only occupy the cells where the hives are located. At the end of the first minute, they occupy all grassy cells adjacent to hives (and still the hives themselves). At the end of the second minute, they additionally occupy all grassy cells adjacent to grassy cells adjacent to hives, and so on.

Given enough time, the bees will end up simultaneously occupying all grassy cells in the forest that are within their reach.

Neither QQ nor the bees can go outside the forest. Also, note that according to the rules above, QQ will always eat honey for an integer number of minutes.

The bees catch QQ if at any point in time QQ finds himself in a cell occupied by bees.

TASK

Write a program that, given a map of the forest, determines the largest number of minutes that QQ can continue eating honey at his initial location, while still being able to get to his home before any of the bees catch him.

CONSTRAINTS

1<=N<=800, the size (side length) of the map

1<=S<=1000, the maximum number of steps QQ can take in each minute

输入:

The next N lines represent the map of the forest. Each of these lines contains N characters

with each character representing one unit cell of the grid. The possible characters and their

associated meanings are as follows:

T denotes a tree

G denotes a grassy cell

M denotes the initial location of QQ and the honeypot, which is also a grassy cell

D denotes the location of QQ’s home, which QQ can enter, but the bees cannot.

H denotes the location of a hive

NOTE: It is guaranteed that the map will contain exactly one letter M, exactly one letter D and at least one letter H. It is also guaranteed that there is a sequence of adjacent letters G that connects QQ to his home, as well as a sequence of adjacent letters G that connects at least one hive to the honeypot (i.e., to QQ’s initial location). These sequences might be as short as length zero, in case QQ’s home or a hive is adjacent to QQ’s initial location.

Also, note that the bees cannot pass through or fly over QQ’s home. To them, it is just like a tree.

输出:

The next N lines represent the map of the forest. Each of these lines contains N characters

with each character representing one unit cell of the grid. The possible characters and their

associated meanings are as follows:

T denotes a tree

G denotes a grassy cell

M denotes the initial location of QQ and the honeypot, which is also a grassy cell

D denotes the location of QQ’s home, which QQ can enter, but the bees cannot.

H denotes the location of a hive

NOTE: It is guaranteed that the map will contain exactly one letter M, exactly one letter D and at least one letter H. It is also guaranteed that there is a sequence of adjacent letters G that connects QQ to his home, as well as a sequence of adjacent letters G that connects at least one hive to the honeypot (i.e., to QQ’s initial location). These sequences might be as short as length zero, in case QQ’s home or a hive is adjacent to QQ’s initial location.

Also, note that the bees cannot pass through or fly over QQ’s home. To them, it is just like a tree.

样例输入:

7 3 TTTTTTT TGGGGGT TGGGGGT MGGGGGD TGGGGGT TGGGGGT THHHHHT 7 3 TTTTTTT TGGGGGT TGGGGGT MGGGGGD TGGGGGT TGGGGGT TGHHGGT

样例输出:

1 2Hints： For the first case, After eating honey for one minute, QQ can take the shortest path directly to the right and he will be home in another two minutes, safe from the bees.Hint

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; class Main { static long[] arr = new long[50]; static long[] sum = new long[50]; static { arr[0] = 1; arr[1] = 1; sum[0] = 1; sum[1] = 2; } public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter( System.out)); int n; for (int c = 2; c < arr.length; c++) { arr[c] = arr[c - 2] + arr[c - 1]; sum[c] = arr[c] + sum[c - 1]; } while ((n = Integer.parseInt(in.readLine())) != -1) { if(n==0) out.write("0 1\n"); else out.write(sum[n-1] + " " + sum[n] + "\n"); } out.flush(); } }

代码过于复杂了吧

https://coding.net/moon/miracle

http://www.realoj.com/problem/7如果楼主不介意，以可以在这个oj上做下，按照你的代码是错的。。。直接复制粘贴你的也是错。。不懂错在哪。

都是一些基础题啊

mark, 很巧妙的实现！

怎么输入两个0程序还没退出

博主的C++功底真是好

第23行：

hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept

终于AC了！next数组还是不好理解啊，mark

加了星号 (*) 表示跳过此数据不读入. 因为scanf是不读取本行回车的

很好！！

程序是错的吧，明显没有判断不和该节点相邻的其他节点是否相互相邻