lightoj1337

maksyuki 发表于 oj 分类，标签:
27 8月 2015
0

1337 - The Crystal Maze

To be more exact, the maze can be modeled as an M x N 2D grid where M denotes the number of rows and N denotes the number of columns. There are three types of cells in the grid:You are in a plane and you are about to be dropped with a parasuit in a crystal maze. As the name suggests, the maze is full of crystals. Your task is to collect as many crystals as possible.

  1. A '#' denotes a wall, you may not pass through it.
  2. A 'C' denotes a crystal. You may move through the cell.
  3. A '.' denotes an empty cell. You may move through the cell.

Now you are given the map of the maze, you want to find where to land such that you can collect maximum number of crystals. So, you are spotting some position x, y and you want to find the maximum number of crystals you may get if you land to cell (x, y). And you can only move vertically or horizontally, but you cannot pass through walls, or you cannot get outside the maze.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing three integers M, N and Q (2 ≤ M, N ≤ 500, 1 ≤ Q ≤ 1000). Each of the next M lines contains N characters denoting the maze. You can assume that the maze follows the above restrictions.

Each of the next Q lines contains two integers xi and yi (1 ≤ xi ≤ M, 1 ≤ yi ≤ N) denoting the cell where you want to land. You can assume that cell (xi, yi) is empty i.e. the cell contains '.'.

Output

For each case, print the case number in a single line. Then print Q lines, where each line should contain the maximum number of crystals you may collect if you land on cell (xi, yi).

Sample Input

Output for Sample Input
14 5 2..#...C#C.##..#..C#C

1 1

4 1

 Case 1:12

Note

Dataset is huge, use faster I/O methods.

 

题目类型：记忆化搜索

算法分析：本题其实求每一个连通块中所有水晶的数量，如果对于每个查询都调用一次DFS或者是BFS会TLE，此时应该使用记忆化搜索的思想使能通过调用一次搜索算法计算出的所有节点(在同一个连通块中)的水晶数量记录下来，然后对于已经计算过的查询操作(查询的坐标在已经计算过的连通块中)，则直接输出相应的记录即可