UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4624. 农场种植

统计 下载数据

Description

农夫约翰想要在一片巨大的土地上建造一个新的农场。 这块土地被抽象为个 R*C 的矩阵。土地中的每个方格都可
以用来生产一种食物:谷物(G)或者是牲畜(L)。下面是一个 R 为 5,C 为 8 的土地的样例:
  12345678
1 GLGGLGLG
2 GGLGGLGL
3 GGLLLGGG
4 LLGLLGLG
5 LGGGLGLL
农夫约翰已经有一套设计好的他想要建造的农场的蓝图。 每一个蓝图被抽象为一个 H*W 的矩阵,其中 H≤R,W≤
C。蓝图中的每个方格表示着农夫约翰想要生产的食物,谷物(G)或是牲畜(L)。下面是一个 H=2,W=3 的蓝图的样
例。
  123
1 GLL
2 LGG
使用这个蓝图,农夫约翰可以在土地上的某个位置建立起实际的农场。这个农场的位置可以用它的左上角的位置来
代表, 比如这个农场被建立在土地上的(r,c)这个位置,这个农场必须整个都建立在这块土地中(也就是说 r + H
 ≤ R 并且 c + W ≤ C) 。如果在土地上的位置(r + i, c + j)的食物种类和蓝图里的位置(i + 1, j + 1)的食
物种类相同(其中 0 ≤ i<H,0 ≤ j<W) ,那么就能出产食物。农夫约翰想要找到这样的农场位置,使得他可以
出产最多的食物(即谷物的格数+牲畜的格数) 。如果有多于一个可能的解,输出最上方的一个,如果仍然有多于
一个可能的解,就输出最作坊的一个。比如对于上面给出的土地和蓝图的样例,最佳的农场位置是(1, 3),这是最
左上方的一个可行的农场,如下图所示:
  12345678
1 GLGGLGLG
2 GGLGGLGL
3 GGLLLGGG
4 LLGLLGLG
5 LGGGLGLL
通过在(1, 3)位置建立农场,农夫约翰可以生产出 5 格的粮食,3 格谷物和2 格牲畜,具体来说,是第一行的一
格谷物和一个牲畜,第二行的一格牲畜和两格谷物。注意位置(2, 5)和位置(3, 2)同样能生产出 5 格谷物,但是
农夫约翰需要的是最靠上中的最靠左的。 在除此以外的任何位置放置农场都只能生产出少于5 格的食物。

Input

输入数据中只有一组土地,第一行包含了两个整数 R 和 C,其中 0 <R,C ≤500,紧接着是 R 行每行包含 C 个字
符来描述这片土地,接下来有一个整数 B,满足 0 <B ≤ 5,表示农夫约翰拥有的蓝图的数量,接下来是 B 个蓝
图,每个蓝图都以包含两个整数 H 和 W 的一行开头,其中 0 <H ≤ R 并且 0 <W ≤ C,紧接着是 H 行,每行 W
 个字母来描述这个蓝图。对于每个蓝图,在一行中输出"Case #X: Y"(没有引号) ,X 是蓝图编号,从 1 开始
,Y 是一组用空格隔开的四个整数组成的输出,前两个整数表示最好的建造农场的位置,接下来两个整数分别表示
可以生产的谷物和牲畜的格数。
R,C ≤ 500,B≤5,H≤R,W≤C

Output

对于每个蓝图,在一行中输出"Case #X: Y"(没有引号) ,X 是蓝图编号,从 1 开始,Y 是一组用空格隔开的四
个整数组成的输出,前两个整数表示最好的建造农场的位置,接下来两个整数分别表示可以生产的谷物和牲畜的格
数。

Sample Input

5 8
GLGGLGLG
GGLGGLGL
GGLLLGGG
LLGLLGLG
LGGGLGLL
3 2
3
GLL
LGG
3 1
L G G 1
4
GGLL

Sample Output

Case #1: 1 3 3 2
Case #2: 1 2 2 1
Case #3: 3 1 2 2

Hint

Source