Icebergs

View as PDF
Submit solution
Points: 12
Time limit: 1.0s
Java 1.75s
Python 3.0s
Memory limit: 256M
Authors:
skyflaren, justinzhu, N3RDSLQYER84, deadfish
Problem type

As the navigator of the newly christened RMS Titanic II, you've been commissioned to plot the ship's course through the ocean, represented by an R by C grid. Keeping with the tradition of the biggest and best, the Titanic II is a large ship, with length L and width W (1 \le L \le R, 1 \le W \le C). Not wanting awful newspaper headlines again, you decide that this time, you will do your best to avoid icebergs, which are represented by the character #. The ship can move freely through open ocean, which is represented by the character ..

Since you lost a lot of money in the first Titanic, management decided to make some cuts. Specifically, the Titanic II cannot rotate. This means that if L = 5, W = 3, the ship cannot rotate and have L = 3 and W = 5. The ship can move in all four cardinal directions, but not diagonally in one move.

You are to find the minimum amount of moves it would take to travel between your starting point at (0,0) (the top-left corner) and the destination (C-1, R-1) (the bottom-right corner) such that any point on your ship is on (C-1, R-1). A move consists of moving once up, left, down, or right.

Note that the ship is not guaranteed to start on a valid position, nor end on a valid position.

For this question, Python users are recommended to use PyPy in order to pass the time limit.

Input Specification

The first line will contain the integers R and C (space separated), representing the rows (y-axis) and columns (x-axis) of the ocean.

The second line will contain the integers L and W (space separated), representing the ship's length (y-axis) and width (x-axis).

The next R lines will contain C characters that are either . or #.

It is guaranteed that the ocean will not be smaller than the Titanic II.

Constraints

For all subtasks:

1 \le L \le R \le 2000, \; 1 \le W \le C \le 2000

Subtask 1 [30%]

1 \le L \le R \le 50, \; 1 \le W \le C \le 50

Subtask 2 [70%]

No further constraints.

Output Specification

Output the minimum amount of moves it would take for the Titanic II to get to its destination. If no such path exists, output -1.

Sample Input 1

5 6
1 2
.....#
..#..#
.#...#
.....#
..#...

Sample Output 1

8

Explanation

00...#       .11..#       ..22.#       ...33#       .....#       .....#       .....#       .....#       .....#
..#..#       ..#..#       ..#..#       ..#..#       ..#44#       ..#..#       ..#..#       ..#..#       ..#..#
.#...#       .#...#       .#...#       .#...#       .#...#       .#.55#       .#...#       .#...#       .#...#
.....#       .....#       .....#       .....#       .....#       .....#       ...66#       .....#       .....#
..#...       ..#...       ..#...       ..#...       ..#...       ..#...       ..#...       ..#77.       ..#.88

Remember that the Titanic II cannot turn, so the single fastest route is three steps right, four steps down and one step right (as outlined above). The diagram above shows the spaces that the Titanic II occupies, for every step.

Sample Input 2

2 3
1 2
...
#..

Sample Output 2

2

Explanation

00.       .11       ...
#..       #..       #22

The Titanic II can move to the right, then down, for a total of 2 steps. The diagram above shows the spaces that the Titanic II occupies, for every step.

Sample Input 3

5 5
2 2
.....
....#
...#.
.....
..#..

Sample Output 3

-1

Explanation

The Titanic II cannot reach the bottom-right corner, as there is no way for a 2 x 2 ship to fit through the icebergs.

Comments


  • 1
    AndyMan68  commented on Oct. 16, 2024, 2:46 a.m. ← edited

    Python users can try pypy as it just barely passes for me but normal Python TLEs (despite its custom time limit)


  • 3
    MstrPikachu  commented on Dec. 14, 2019, 3:04 a.m.

    Fat Man and Walking


    • 1
      skyflaren  commented on Dec. 14, 2019, 8:41 p.m.

      The real problem statement o.O we still have that paragraph somewhere...


      • 1
        MstrPikachu  commented on Dec. 14, 2019, 9:28 p.m.

        fix it


        • 2
          N3RDSLQYER84  commented on Dec. 14, 2019, 9:47 p.m.

          Fatman may or may not return in the form of Fatman and :bread:


          • 2
            skyflaren  commented on Dec. 15, 2019, 6:42 p.m.

            :gasp: ||spoiler alert||


    • 4
      N3RDSLQYER84  commented on Dec. 14, 2019, 3:09 a.m.

      :eyes:


      • -10
        AlanL  commented on Dec. 14, 2019, 7:56 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


      • 3
        MstrPikachu  commented on Dec. 14, 2019, 3:17 a.m.

        Can I play Minecraft with you