Mackenzie New Year's Challenge P5 - Jelly

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 4.0s
Memory limit: 256M

Author:
Problem type

Julie had a spooky nightmare. She is stuck in a Jelly! She has to eat her way out. Being a smart human being, her sub-conscience created a very sophisticated jelly. The jelly is composed of blocks. Different parts of the jelly have varying densities. The densities of each block are represented by single digit number, 1 – 9. The jelly is a rectangular prism, with dimensions, X, Y and Z signifying the length, height and width in blocks, respectively. Julie can only eat in the following directions: up, down, left, right, forward and backwards. While dreaming, Julie has an infinitely big stomach. However, she's dazed and wants to exit the jelly as quickly as possible. As the density of the block is directly correlated with the time it takes to eat, Julie wants to eat a block path with minimal total density. Find the minimum sum of densities of the blocks that Julie has to eat to exit the jelly. Julie exits the jelly once she reaches any side of the jelly.

Julie in a jelly

Input Specification

Input begins with X, Y and Z space separated on a single line, signifying the dimensions of the jelly. The next Z \times Y lines contain Z blocks of Y lines with X characters, denoting the densities of the blocks, or J, to indicate the position of Julie.

1 \le X, Y, Z \le 150

Hint: You may need fast IO methods for this problem to pass large test cases.

Output Specification

Integer T denoting the minimum sum of the densities of jelly that Julie has to eat to exit the jelly.

Sample Input

3 3 3
989
898
989
989
8J8
989
989
878
989

Sample Output

7

Comments


  • 0
    aeternalis1  commented on Aug. 7, 2017, 4:59 p.m. edited

    Is Dijkstra's algorithm the intended solution for this problem? Is it viable for python?


  • 3
    MathBunny123  commented on March 14, 2016, 11:42 a.m.

    It seems like the value got increased to 15 points from 10 points, so it shows up as 10/15 on profiles. If you rerun it it becomes 15 points :)


    • 3
      FatalEagle  commented on March 14, 2016, 4:21 p.m.

      It's been changed back. I don't know why the author decided to change the point value, but it's certainly not worth 15.


  • 0
    minecraftyugi  commented on Dec. 30, 2015, 7:07 p.m.

    Which variable tells how many blocks are in each line?


    • 2
      aurpine  commented on Dec. 31, 2015, 12:01 p.m. edited

      Imagine it 2D first. There are Y lines with X characters. There are Z batches of lines, because there are Z layers of these 2D blocks, which makes it 3D.


    • 0
      XIAOAGE  commented on Dec. 30, 2015, 7:33 p.m.

      z


      • 0
        minecraftyugi  commented on Dec. 30, 2015, 7:47 p.m.

        Is the input of lines given in a specific order? Like does it start in a corner and then move in a specific direction? I am really confused


        • 0
          XIAOAGE  commented on Dec. 30, 2015, 8:32 p.m. edited

          U can think x as the number of floors, and the first y rows represent the arrangement of the first floor with z values on each row. But anyway, u don't really need visualize the whole thing, just treat the problem in the same way as 2-D ones.