I - Garden 2 Editorial /

Time Limit: 3 sec / Memory Limit: 976 MB

配点：1500 点

問題文

時は 2022 年 6 月 20 日。AtCoder は創立 10 周年を記念し、会社の前に庭が作られました。
庭は H 行 W 列のマス目で表され、上から i 行目、左から j 列目にあるマスを、マス (i, j) とします。
各マスには 1 つの花が植えられています。マス (i, j) の花の美しさは A_{i, j} です。

例えば、以下のような図が庭の例です。ただし各マスに書かれている数は花の綺麗さです。

さて、あなたはいくつかの花を伐採し、 美しい庭 を作りたいです。美しい庭とは、以下のような条件を満たすものです。

  • 伐採されていない花のマス (a, b) から、別の伐採されていない花のマス (c, d) まで、上下左右に隣り合う伐採されていない花のマスのみを辿って、同じマスを二度通らずに行く方法はちょうど 1 通り存在する。
  • 全ての伐採されていない花のマス (a, b), (c, d) ((a, b) \neq (c, d)) について上が成り立つ。

例えば、以下のような伐採の仕方をすると、美しい庭になります。

一方、以下のような伐採の仕方をすると、美しい庭にはなりません。

庭の得点 は、伐採されていない花の綺麗さの合計です。ただし、庭が美しい庭でなければ、庭の得点は 0 点となります。
例えば、上の図の庭 A の得点は 20 点、庭 B の得点は 60 点、庭 C, D, E までの得点は 0 点です。
そのとき、庭の得点が出来るだけ高くなるような伐採方法を出力してください。

入力

入力は以下の形式で標準入力から与えられます。 

H W
A_{1, 1} A_{1, 2} A_{1, 3} ... A_{1, W}
A_{2, 1} A_{2, 2} A_{2, 3} ... A_{2, W}
A_{3, 1} A_{3, 2} A_{3, 3} ... A_{3, W}
...
A_{H, 1} A_{H, 2} A_{H, 3} ... A_{H, W}

出力

以下のように H 行に渡って出力してください。 

c_{1, 1}c_{1, 2}c_{1, 3} ... c_{1, W}
c_{2, 1}c_{2, 2}c_{2, 3} ... c_{2, W}
c_{3, 1}c_{3, 2}c_{3, 3} ... c_{3, W}
...
c_{H, 1}c_{H, 2}c_{H, 3} ... c_{H, W}

ただし、c_{i, j} は、マス (i, j) を伐採 しない 場合 #、伐採 する 場合 . としてください。

制約

  • H, W は 1 以上 500 以下の整数
  • A_{i, j} は 1 以上 9 以下の整数

テストケースの生成について

テストケースは、以下のように作成されている。

  • 各テストケースごとに、H, W の値が決まっている。これに関しては、小課題・得点の項を参照すること。
  • A_{i, j} については、各 (i, j) (1 \leq i \leq H, 1 \leq j \leq W) について 1 以上 9 以下の整数から一様な確率で選ぶ。

小課題・得点

採点に使われるテストケースは 15 個存在する。各テストケースごとに 100 点満点で採点され、100 \times 15 = 1500 点満点でこの問題の点数が決定する。
各ケースの採点方法は以下のようである。ここでは、そのケースでの「庭の得点」を L とし、また、L' = L \div (H \times W) とする。

(☆) H = 5, W = 5 (ケース 1, 2, 3) の場合、H = 5, W = 500 (ケース 4, 5, 6) の場合の採点方法

  • 0.00 \leq L' < 2.00 のとき、0 点
  • 2.00 \leq L' < 3.33 のとき、0 + (L - 2.00) \times 21 点
  • 3.33 \leq L' < 3.93 のとき、28 + (L - 3.33) \times 40 点
  • 3.93 \leq L' < 4.03 のとき、52 + (L - 3.93) \times 480 点
  • 4.03 \leq L' のとき、100 点

(★) H = 500, W = 500 (ケース 7, 8, 9, 10, 11, 12, 13, 14, 15) の場合の採点方法

  • 0.00 \leq L' < 2.00 のとき、0 点
  • 2.00 \leq L' < 3.33 のとき、0 + (L - 2.00) \times 21 点
  • 3.33 \leq L' < 3.78 のとき、28 + (L - 3.33) \times 75 点
  • 3.78 \leq L' < 3.84 のとき、61 + (L - 3.78) \times 650 点
  • 3.84 \leq L' のとき、100 点

2.00 \leq L' \leq 4.05 の場合の、L' の値と得点の関係を表したグラフは以下のようになる。

注意

0 点と採点されたテストケースが存在する場合に限り、WA と判定されることにご注意ください。
WA でも得点がもらえている場合があること、AC でも満点ではない場合があることにご注意ください。

この問題はマラソン型課題であるため、全てのケースで満点を取れることが保証されていないことにご注意ください。作問者の解法が必ず満点とは限りません。
また、この問題に関して、満点の基準を大幅に超える提出が多数見られた場合、得点の式が変更される場合が非常に小さい確率ですがあります。ご了承ください。なお、競技開始 3 時間後以降は、得点の変更がないことが保証されております。

入力例 1

3 3
1 2 3
4 5 6
7 8 9

出力例 1

#.#
###
#.#

出力例 1 のような伐採方法を行うと、庭の得点は 1 + 3 + 4 + 5 + 6 + 7 + 9 = 35 点となります。
なお、このテストケースは採点用データに含まれないことにご注意ください。

入力例 2

4 5
4 1 8 2 6
2 2 1 2 5
3 5 1 9 2
5 1 2 3 6

出力例 2

#.###
#...#
#####
#.#.#

この入力例は、問題文中の画像に対応します。
また、この出力例は問題文中の例 B に対応し、庭の得点は 60 となります。そのとき、L' の値は 60 \div 20 = 3.00 となります。
ちなみに、庭の得点が 62 となるような出力も存在しますが、この問題では必ずしも最も庭の得点が最大となるような出力をする必要はないことにご注意ください。
なお、このテストケースも採点用データに含まれないことにご注意ください。

Max Score：1500 points

Problem Statement

June 20th, 2022 is the day of 10 year anniversary from the launch of AtCoder.
On this day, a garden was built in front of AtCoder to celebrate this anniversary.

The garden is represented as a H \times W grid. The cell that i-th row from the top and the j-th column from the left is denoted as cell (i, j).
In each cell, there is a flower. The beauty of flower in cell (i, j) is A_{i, j}.

An example of the garden is as follows: (The case of H = 4, W = 5)

You should make a beautiful garden by cutting flowers in some cells. The condition which should satisfy to be a beautiful garden is as follows:

  • For all a, b, c, d that both flowers in cell (a, b) and cell (c, d) ((a, b) \neq (c, d)) has not been cut, it satisfies following condition.
  • From (a, b) to (c, d), there is exactly 1 ways to go, by moving either of up, right, left, down by one square repeatedly, without passing the same cell twice.

For example, if you cut some flowers like A, and B, it will be a beautiful garden.

For example, if you cut some flowers like C, D, E, it will not be a beautiful garden.

The score of garden will be calculated as follows:

  • If the garden is not a beautiful garden, the score will be 0.
  • If the garden is a beautiful garden, the score will be the total beuaty of flowers which has not been cut.

For example, the score of garden A is 20, the score of garden B is 60, and the score of garden C, D, E are 0.
Print a way of cutting flowers that score of garden is as high as you can.

Input

Input is given from Standard Input in the following format: 

H W
A_{1, 1} A_{1, 2} A_{1, 3} ... A_{1, W}
A_{2, 1} A_{2, 2} A_{2, 3} ... A_{2, W}
A_{3, 1} A_{3, 2} A_{3, 3} ... A_{3, W}
...
A_{H, 1} A_{H, 2} A_{H, 3} ... A_{H, W}

Output

Print H likes as follows: 

c_{1, 1}c_{1, 2}c_{1, 3} ... c_{1, W}
c_{2, 1}c_{2, 2}c_{2, 3} ... c_{2, W}
c_{3, 1}c_{3, 2}c_{3, 3} ... c_{3, W}
...
c_{H, 1}c_{H, 2}c_{H, 3} ... c_{H, W}

c_{i, j} should be # if you won't cut a flower in cell (i, j), and . if you will cut flower in cell (i, j).

Constraints

  • H, W are integers between 1 and 500.
  • A_{i, j} is an integer between 1 and 9.

About Testcases

Testcases are generated as follows:

  • For each testcase, H, W is determined. You should look subtasks/scoring section to know about the exact value.
  • A_{i, j} is random integer between 1 and 9. The probability that A_{i, j} = 1 is 1 in 9. It is the same for A_{i, j} = 2, 3, 4, ..., 9.

Subtasks and Scoring

There are 15 testcases that are used for grading. Since max score per each case is 100. Max score of this problem is 100 \times 15 = 1500.
For each case, it will be graded as follows. Let L be the score of garden in your output, and let L' be L \div (H \times W).

(i) When H = 5, W = 5 (Case #1, #2, #3), or H = 5, W = 500 (Case #4, #5, #6):

  • If 0.00 \leq L' < 2.00 : 0 points
  • If 2.00 \leq L' < 3.33 : 0 + (L - 2.00) \times 21 points
  • If 3.33 \leq L' < 3.93 : 28 + (L - 3.33) \times 40 points
  • If 3.93 \leq L' < 4.03 : 52 + (L - 3.93) \times 480 points
  • If 4.03 \leq L' : 100 points

(ii) When H = 500, W = 500 (Case #7, #8, #9, #10, #11, #12, #13, #14, #15):

  • If 0.00 \leq L' < 2.00 : 0 points
  • If 2.00 \leq L' < 3.33 : 0 + (L - 2.00) \times 21 points
  • If 3.33 \leq L' < 3.78 : 28 + (L - 3.33) \times 75 points
  • If 3.78 \leq L' < 3.84 : 61 + (L - 3.78) \times 650 points
  • If 3.84 \leq L' : 100 points

This is the graph which describes the relation between L' and score when 2.00 \leq L' \leq 4.05.

Note

The verdict will be AC if there is no testcase which is graded 0 points.
It means it is not always full-score if you got AC, and it also means even if you got WA it is possible that you got some partial score.

Since this problem is marathon-match like optimization task, it is not guaranteed that there is a full-solution for all cases. Solution of problemsetter is not always full score. In addition, it is very unlikely, but if many people wrote the solution which significantly over the creterion of full score, changing scoring formula is also possible. It is guaranteed that there is no change of scoring formula after 3 hours from the beginning of this contest.

Sample Input 1

3 3
1 2 3
4 5 6
7 8 9

Sample Output 1

#.#
###
#.#

In this example, the score of garden is 1 + 3 + 4 + 5 + 6 + 7 + 9 = 35.
Note: This input is not included in datasets for grading.

Sample Input 2

4 5
4 1 8 2 6
2 2 1 2 5
3 5 1 9 2
5 1 2 3 6

Sample Output 2

#.###
#...#
#####
#.#.#

This example is as same as the example picture that written in problem statement.
Also, this sample output is as same as garden B that written in problem statement. The score of garden is 60, and value of L' is 3.0.
Actually, there is a solution which the score of garden is 62 :)
Note: This input is also not included in datasets for grading.