#3281. 「JOISC 2020 Day4」传奇团子师傅

题目类型:答案提交 评测方式:Special Judge
上传者: ksyx

题目描述

题目译自 JOISC 2020 Day4 T2「伝説の団子職人 / Legendary Dango Maker

你是一位糯米团子大师,现在你正在串团子。

你面前有一个 R C 列的网格,每格里面放着一个粉、白、绿三色之一的团子。你每次会横向、竖向或斜向选三个连续的团子并将他们按顺序串到一起。其中,按顺序指竖直方向的团子只能以上、中、下或下、中、上的顺序串,而不能以中、上、下或中、上、下的顺序串,其他顺序以此类推。这样,你就获得了一串团子。

当且仅当一串团子的颜色顺序是绿、白、粉或粉、白、绿时,我们把这串团子称为美丽串,请求出串取最多的美丽串的方法。

输入格式

本题共六组数据。

数据的第一行两个以空格分隔的整数 R,~C

接下来 R 行每行一个仅含字符 PWG 的字符串 D_i ,第 j 个字符 D_{i,j} 表示第 i j 列的团子颜色。

输出格式

输出 R 行,每行一个长度为 C 的仅含字符 PWG|-\/ 的字符串 S_i ,第 j 个字符 S_{i,j} 表示第 i j 列团子的串法。

  • 如果 S_{i,j} |,表示你想把该格及其上、下方一格的团子串起来。
  • 如果 S_{i,j} -,表示你想把该格及其左、右方一格的团子串起来。
  • 如果 S_{i,j} \,表示你想把该格及其左上、右下方一格团子串起来。
  • 如果 S_{i,j} /,表示你想把该格及其右上、左下方一格团子串起来。
  • 否则, S_{i,j} 应与 D_{i,j} 相同。

样例

样例输入 1

3 4
PWGP
WGPW
GWPG

样例输出 1

P-GP
WGP|
G-PG

样例解释 1

本样例中,你做了三串美丽的团子。

注意,在本样例中的 W G P 不是一种美丽的团子串。

样例输入 2

3 4
PWWP
WWWW
PGGP

样例输出 2

PWWP
W\/W
PGGP

样例解释 2

本样例中,你做了两串美丽的团子。

数据范围与提示

数据范围

对于 100\% 的数据,有 3\le R,~C\le 500 |D_i|=C,~D_{i,j}\in\{\texttt{P,}~\texttt{W,}~\texttt{G}\}

评分方式

本题的得分以以下方式计算。

对于每个测试点,我们定义四个参数 S,~X,~Y,~Z 。其中, S 表示该测试点的分值。各测试点的参数值如下:

测试点 S X Y Z
1 15 44000 47000 47220
2 39000 41700 41980
3 45000 51000 51390
4 18000 19000 19120
5 20 43000 48200 48620
6 44000 46000 46500

对于每个测试点,令 N 表示你提交中所做出来的美丽团子串数,你的分值由以下方式计算得出:

  • 如果 N < X ,你的分数为 0
  • 如果 X \le N < Y ,你的分数为 \frac{N - X}{2 (Y - X)} \times S
  • 如果 Y \le N < Z ,你的分数为 \left( \frac{1}{2} + \frac{N - Y}{2 (Z - Y)} \right) \times S
  • 如果 Z \le N ,你的分数为 S

你本题的分数为各测试点分数之和四舍五入到整数后的结果。

但是,如果你的输出无效,例如按照你的输出中的 |-\/ 字符无法做出美丽的团子串,或者 PWG 与输入不一致,或者输出格式错误,将被判为 0 分。

可视化工具

本题附加文件中提供了一个可视化工具,可以将输入数据和输出数据可视化。

如果要使用可视化工具,请用浏览器打开 visualizer.html 并选取文件(译者注:此处应该指输入、输出文件)。注意,可视化工具不检查你所选取文件的格式是否正确。如果格式不正确,可能无法正常执行可视化操作。另外,RC 过大时也不会执行可视化操作。

编辑器加载中 …