Statistics

Problem Statement for "WaterBot"

Problem Statement

Every spring, your grandmother plants a garden. Since she is in her later years, she often needs help with watering the plants. Of course, you always offer a helping hand but you also have a more permanent solution. You call your invention "I can't believe it works!", and it is about to bring a revolution to the garden-watering industry. Your creation is a robot that will water the garden, taking the least time possible. 
Your job is to implement part of the software that will guide the robot.  The robot may only move and see in the four cardinal directions: North, East, West or South.  The garden will be represented by the String[] garden, which consists of digits, dots, a single 'R' and a single 'W' (quotes for clarity).  Each digit will represent how many units of  water a plant in that location needs.  The character '.' marks an empty location, 'R' marks the robot's current location and 'W' marks the location of a well (quotes for clarity).  During the robot's travels, it may not step on any plants (that would only upset your grandmother) or the well (that would really make you angry).  

Given garden and carryLimit, calculate and return the minimum amount of time needed to water all plants if the robot may only carry at most carryLimit units of water at any time.  It takes n time units to water a plant that needs n units of water.  In addition, m time units are needed to get m units of water from the well and each step in any direction takes 1 unit of time.  The robot can change the direction in which it is facing instantly, taking zero time units.  The robot may only water a plant if it is directly next to it; the same requirement must be met when taking water from the well.  Finally, the robot may water only one plant at a time.  If it is impossible to water all plants, return -1.

Definition

Class:
WaterBot
Method:
minTime
Parameters:
String[], int
Returns:
int
Method signature:
int minTime(String[] garden, int carryLimit)
(be sure your method is public)

Notes

  • Initially, the robot is holding zero units of water.
  • The robot may not step out of the garden at any time.

Constraints

  • garden will contain between 1 and 50 elements, inclusive.
  • Each element in garden will contain between 1 and 50 characters, inclusive.
  • All elements in garden will be of the same size.
  • Each element in garden may only contain the following characters: 'W', 'R', '.', '1', '2', '3', '4', '5' (quotes for clarity).
  • garden will contain exactly one occurrence of 'R' and 'W'.
  • garden will contain between 0 and 4 digits, inclusive.
  • carryLimit will be between 1 and 5, inclusive.

Examples

  1. {"..................................................", ".5..............................................5.", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "........................W.........................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".5..............................................5.", "........................R........................."}

    5

    Returns: 378

    The worst possible case.

  2. {"..................................................", ".5..............................................5.", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "........................W.........................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".5..............................................5.", "........................R........................."}

    1

    Returns: 1818

    Same case as the first, but smaller carryLimit. The return value is larger, but there are less states - so this case runs a bit faster.

  3. {"5....", ".....", ".....", ".....", "...RW"}

    5

    Returns: 16

    The robot begins its journey next to the well. It takes 5 units of time to collect 5 units of water. Then, it takes 6 units of time to move to the only plant that needs watering. At last, the robot will water the plant for 5 units of time. The total time required is 16 units.

  4. {"3.2..", ".....", ".....", "....R", "....W"}

    5

    Returns: 16

    Once again, the robot is next to the well. The most efficient schedule is to collect 5 units of water, then water both plants without returning to the well.

  5. {"3.3..", ".....", ".....", "....R", "....W"}

    3

    Returns: 26

  6. {"5.5..", ".....", ".....", "....R", "....W"}

    5

    Returns: 34

  7. {"5.5.5", ".....", ".....", "....R", "....W"}

    5

    Returns: 48

  8. {".5555", ".....", ".....", "....R", "....W"}

    3

    Returns: 85

  9. {".5555", ".....", ".....", "....R", "....W"}

    2

    Returns: 107

  10. {"R.......", "..5.5...", ".5......", "..5.....", "........", ".......W"}

    5

    Returns: 92

  11. {"R.....55", "......55", "........", "........", "........", ".......W"}

    2

    Returns: -1

    The robot cannot reach the top-right plant without stepping on at least one other plant.

  12. {"R.......", "........", "....5...", "...5W5..", "....5...", "........"}

    4

    Returns: -1

    The robot cannot get any water from the well.

  13. {"R.......", "....5...", "........", "....W...", "........", "........"}

    5

    Returns: 16

  14. {".1", ".2", ".3", ".4", "R.", "W."}

    5

    Returns: 28

  15. {"R....", ".....", ".....", ".....", "....W"}

    5

    Returns: 0

    There are no plants to water here.

  16. {"..................................................", ".5..............................................5.", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "........................W.........................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".5..............................................5.", "........................R........................."}

    2

    Returns: 1008

    same as tests 0 and 1, but different carryLimit

  17. {"..................................................", ".5..............................................5.", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "........................W.........................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".5..............................................5.", "........................R........................."}

    3

    Returns: 738

  18. {"..................................................", ".5..............................................5.", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "........................W.........................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".5..............................................5.", "........................R........................."}

    4

    Returns: 596

  19. {"1......1", "........", "...W....", "...R....", "........", "1......5"}

    4

    Returns: 41

    A miniature version of test 17. I haven't figured out a path that takes 41 time units yet...

  20. {".......1", "........", "........", "....R...", "W.......", ".....4..", "....3...", "..3....."}

    2

    Returns: 71

    {".......1", "........", "........", "....R...", "W.......", ".....4..", "....3...", "..3....."}

  21. { ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", "........5........................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", "............4....................................", ".................................................", ".................................................", "............................................W....", ".................................................", ".................................................", ".................................................", ".............5...................................", ".................................................", ".................................................", ".................................................", "..............................5..................", ".................................................", ".................................................", ".................................................", ".................................................", "..............................................R..", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", ".................................................", "................................................." }

    4

    Returns: 365

  22. { "W.................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".................................................5", ".................................................5", "..............................................55.R" }

    1

    Returns: 3802

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: