COCI '14 Contest 6 #3 Meteor

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M
Problem type

A photograph of a small meteor of an unusual shape was posted on the Internet. In that photo, the meteor is falling from a great height towards an uneven ground. There was also a photograph taken just after the meteor fell, but it is sadly lost and needs to be reconstructed.

The photograph is simplified and represented as a matrix of characters. The character X represents a part of the meteor, the character # represents a part of the ground and the rest of the image (air) consists of the characters ..

The meteor is connected. In other words, a path exists between each two parts of the meteor that passes only through the meteor and consists of steps up, down, left and right. Also, all parts of the ground are connected in the same way.

In the given photograph, the meteor is located strictly above ground. More precisely, there is at least one row of air (dots), the meteor is completely above it and the ground is completely below it. In addition, the entire bottom row of the image is a part of the ground.

The meteor was falling vertically downward. When it fell on the ground, it kept its shape, and the same goes for the ground. Reconstruct the photograph after the meteor fall!

Input

The first line of input contains the integers R and S (3 \le R, S \le 3\,000), the number of rows and the number of columns of the photograph.

The following R lines contain the photograph described in the task.

Output

Output the required photograph (dimensions R \times S) after the meteor fall.

Sample Input 1

5 6
.XXXX.
...X..
......
#..###
######

Sample Output 1

......
.XXXX.
...X..
#..###
######

Sample Input 2

9 7
XXX.XXX
X.XXX.X
X..X..X
X.....X
.......
.#...#.
.##.##.
.#####.
#######

Sample Output 2

.......
.......
.......
.......
XXX.XXX
X#XXX#X
X##X##X
X#####X
#######

Comments


  • 0
    grammer  commented on Dec. 17, 2023, 4:10 p.m. ← edit 2

    Python 3 barely AC, #5: AC [0.570s<0.6s,17.55 MB<64]; PyPy 3 MLE, #5: MLE[0.210s<0.6s,74.80 MB>64]


  • 1
    bobhob314  commented on Feb. 7, 2015, 10:39 p.m. ← edited

    It seems that in Python, simply creating a two-dimensional array of all of the characters in the 'photograph' uses up too much memory, even with PyPy.


    • 1
      FatalEagle  commented on Feb. 7, 2015, 10:53 p.m.

      Then use C++. Not all problems are solvable with Python.


      • 1
        bobhob314  commented on April 10, 2015, 8:14 p.m.

        Has the memory limit been extended for the problem as well?

        (In re Ship and Shop comment)


        • 0
          FatalEagle  commented on April 11, 2015, 2:09 a.m.

          This problem comes from a contest where the time and memory limits are explicitly stated (unlike past CCCs, where you could run it on your own server if you wished).


          • 1
            bobhob314  commented on June 29, 2015, 4:11 p.m.

            Upon further research, the official hsin.hr/coci solution is in Python and TLEs on your judge.


            • -3
              FatalEagle  commented on June 29, 2015, 9:49 p.m.

              It doesn't matter. As long as there is at least one solution in any language that can pass, the problems and constraints are considered valid.


        • -1
          Xyene  commented on April 11, 2015, 2:07 a.m.

          Not yet. There are a number of problems that would benefit from extended resource limits, though.


      • 2
        omaewamoushindeiru  commented on Feb. 8, 2015, 4:01 a.m.

        Hey Fatal,

        Just wondering if it's possible to do this question using Java without having to time out.


        • -1
          FatalEagle  commented on Feb. 8, 2015, 3:19 p.m.

          No idea. The input and output are pretty large for this problem, which Java might have issues with. As you can see, COCI favors C/C++/Pascal.


      • 4
        bobhob314  commented on Feb. 7, 2015, 10:54 p.m.

        But that would entail learning C++...


        • 0
          kobortor  commented on Feb. 8, 2015, 12:42 a.m.

          Hob get rekt by c++ master race