Background

upd on 2023/11/01: The partial scoring for this problem has been fixed.

Translated from CEOI 2013 Day 2.

Sara is a hard-working farmer who owns a large rectangular piece of land. Her land is divided into a grid of cells, with a total of $5\times R$ rows and $5\times C$ columns. In addition, there is a horizontal fence every five rows and a vertical fence every five columns. These fences divide the land into $R\times C$ regions of size $5\times5$, called fields.

The two most common problems on this farm are birds and drought. To fight birds, some fields contain a scarecrow. A scarecrow (if present) occupies one cell, and each $5\times5$ field can contain at most one scarecrow.

During dry periods that can last for months, Sara uses sprinklers to water her crops. Each sprinkler has three nozzles: one main nozzle and two side nozzles. It occupies exactly three cells and waters all of them. The side nozzles always occupy the two cells adjacent to the main nozzle (up, down, left, or right). Therefore, the three cells watered by a single sprinkler are as shown:

Sara wants to place exactly one sprinkler nozzle on every cell that is not occupied by a scarecrow. Cells containing a scarecrow cannot contain any sprinkler nozzle. Also, no nozzle may be placed outside Sara’s land. The three cells watered by one sprinkler do not have to belong to the same $5\times5$ field: they may also belong to neighboring fields. In that case, Sara must drill a hole in the fence between the two adjacent fields watered by the same sprinkler.

Problem Description

This is an output-only problem. You will be given $10$ input files, and you only need to submit the corresponding output files. You can download the input files from watering.in.zip in the attachments.

Submit any feasible watering plan that satisfies all requirements.

If multiple solutions exist, you may submit any of them.

Input Format

The first line contains two integers $R$ and $C$ ($1≤R,C≤100$), which represent the size of Sara’s land.

The next $6\times R-1$ lines each contain a character sequence of length $6\times C-1$. They represent Sara’s fields and the fences between them. Even though the fences are actually infinitely thin, they are represented by characters.

Each cell is represented by one character. A dot . means an empty cell, and a # means a scarecrow. Vertical fences are represented by |, horizontal fences by -, and intersections by +.

Output Format

The output file should contain a text representation of the land in the same format as the input file, with a valid sprinkler arrangement. Each hole in a fence should be represented by an underscore character _. All empty cells (dots) in the input file must be replaced by lowercase letters a - z, satisfying the following rules:

1. Any three cells watered by the same sprinkler must be labeled with the same letter, even if they are not all in the same $5\times5$ field.
2. If two adjacent cells in the same field are watered by different sprinklers, they must be labeled with different letters.
3. If two adjacent cells in different fields are watered by different sprinklers, and there is a hole in the fence between them, then they must be labeled with different letters (but what is the point of drilling a hole like that).
4. It is allowed to label adjacent cells from different fields with the same letter, as long as all previous rules are satisfied.

2 2
.....|.....
.....|.....
...#.|.....
.....|.....
.....|.....
-----+-----
.....|.....
.....|.....
.....|.....
.....|.....
.....|.....

aaacc|dxxxa
bbbce|dyyya
ddd#e|dzzza
ccbae|fccbb
cbbaa|ffcdb
-----+---_-
ssrrr|tttdd
saaax_xxeee
yxbbb|zdaaa
yxccc|zdbbb
yxddd|zdccc

Hint

Each test case is worth $10$ points. If your output is invalid, you will get zero points for that test case. If your output is valid, it will be scored as follows:

• If the number of holes in fences is at most $R\times C$, the score is $10$ points.
• Otherwise, the score is $5$ points.

In $4$ of the $10$ test inputs, each field contains one scarecrow.

SPJ provider:

open the files in the attachments using Notepad or WordPad.

Translated by ChatGPT 5