DMOPC '19 Contest 5 P6 - Cecilia's Computational Crisis

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 128M

Problem type

Despite their best efforts, the persistent downpour in the city of Hail has left its citizens in shambles. As an experienced engineer, Cecilia has taken on a volunteer job in managing flood control. In her job, she creates "sandbag plans" to tell workers where to place sandbags in their respective work areas.

First, she is given a constraint plan, a grid with N rows and M columns consisting of only ., X, and ? characters. To generate a sandbag plan from this constraint plan, she replaces all ? characters with either . or X, indicating that a sandbag should or should not be placed in this cell, respectively. In her research, Cecilia has found that a constraint plan is effective if all rows in the constraint plan are pairwise distinct. Cecilia is interested in determining whether an effective plan can be made. Of course, doing this by hand is very time-consuming, so Cecilia needs your help!

Input Specification

The first line contains two space-separated integers, N, the number of rows in the constraint plan, and M the number of columns in the constraint plan.
The next N lines contain a string of length M, consisting of ., X, or ?.

Output Specification

If it is possible to create an effective plan from the constraint plan, output YES on the first line, followed by any effective constraint plan.
Otherwise, output NO.


In all subtasks,
1 \le N, M \le 400

Subtask 1 [5%]

1 \le N,M \le 2

Subtask 2 [5%]

1 \le N \le 2

Subtask 3 [10%]

1 \le N \le 8

Subtask 4 [80%]

No additional constraints.

Sample Input 1

4 4

Sample Output 1


Sample Input 2

5 5

Sample Output 2


Explanation of Sample 2

No effective plan exists for the given constraint plan.


There are no comments at the moment.