← 返回题目列表

AtCoder · ddcc2017_qual_d

D. 石头

中文机器翻译题面 查看原题

配点 : 600 点

問題文

南北方向 H ,东西方向 W 有一个网格状的花园,从北面看去。 从西数第 i(1≦i≦H) th,从西边 j(1≦j≦W) 第一个方格 比方说 (i,j) 。

但是, H 和 W 是偶数。

每个方格最多有石头。 1 还有 1 石头被放置在不止一个方格中。

初始花园状态是一个字符串 使用 m_{i,j} , 如果 (i,j) 中有一块石头 m_{i,j} = S,如果没有石头 它被给出为 m_{i,j} = . 。

这些石头 1 将它们一一删除。

移走石头后,如果花园里石头的排列是南北对称的, 如果 A 的幸福水平东西方向对称,那么 你会得到 B 幸福。

然而,当南北方向和东西方向都对称时, 假设您可以获得 A+B 的幸福水平。

求当所有石头按自由顺序移走时可以获得的最大幸福感。

南北方向对称意味着以下内容成立。

  • 全部 在 i,j(1≦i≦H,1≦j≦W) 中 (i,j) 中有一块石头 (H+1-i,j) 里还有一块石头。 如果 (i,j) 中没有石子 (H+1-i,j) 中没有石头。

另外,东西方向对称是指满足以下条件。

  • 全部 在 i,j(1≦i≦H,1≦j≦W) 中 (i,j) 中有一块石头 (i,W+1-j) 里还有一块石头。 如果 (i,j) 中没有石子 (i,W+1-j) 中没有石头。

制約

  • 2≦H,W≦200
  • H,W 是偶数
  • 1≦A,B≦10000
  • m_{i,j} 是 S 或 .
  • 放置石头的方格是 1 个以上
  • H,W,A,B 以整数形式给出

入力

输入是按以下格式从标准输入给出的。

H W
A B
m_{1,1}...m_{1,W}
:
m_{H,1}...m_{H,W}

出力

可以获得的最大幸福程度是 x 时, x 。


入力例 1

4 4
2 5
....
.SS.
..S.
....

出力例 1

12

例如, 如果按照 (3,3),(2,2),(2,3) 的顺序移除石头, 当(3,3) 石头被移除后,它变得东西向对称, 当你移除 (2,3) 石头后,东西方向和南北方向变得对称,获得的幸福度为 12 变为。


入力例 2

2 2
4 7
.S
S.

出力例 2

11

无论你以什么顺序移除石头,只有当你移除最后一块石头时,你才会获得幸福。


入力例 3

4 8
9 13
.SS.....
.SS.....
.SS.....
.SS.....

出力例 3

49