Statistics

Problem Statement for "DriveCar"

Problem Statement

Little John likes to play driving games. One of his favorite games involves a horizontal three-lane road divided into cells. The cells are numbered 0, 1, 2, etc. from left to right, and the lanes are numbered 0, 1, 2 from top to bottom. The car is initially located in the middle lane in the leftmost cell (lane 1, cell 0). The goal of the game is to reach any lane of the rightmost cell without hitting any obstacles or leaving the road.

The car moves horizontally one cell at a time. Each time it moves to the next cell, it can either stay in the same lane or move diagonally to an adjacent lane. More formally, if the car is in lane i, cell j, then after the next move, it can be in one of the following lanes of cell j+1: i, i-1 (only if i>0), or i+1 (only if i<2).

The road is given as a String[] road, where the j-th character of the i-th element is the content of lane i, cell j. '.' represents open road and '#' represents an obstacle. The car hits an obstacle if it ends a move on a '#' character. Return the fewest number of lane changes necessary to reach the rightmost cell without hitting any obstacles or leaving the road. If it is impossible to reach the rightmost cell, return -1 instead.

Definition

Class:
DriveCar
Method:
minNumberOfDrifts
Parameters:
String[]
Returns:
int
Method signature:
int minNumberOfDrifts(String[] road)
(be sure your method is public)

Constraints

  • road will contain exactly 3 elements.
  • All elements of road will contain the same number of characters.
  • Each element of road will contain between 1 and 50 characters, inclusive.
  • Each character in each element of road will be '.' or '#'.
  • The leftmost character of element 1 of road will be '.'.

Examples

  1. {"....", "....", "...."}

    Returns: 0

    John doesn't need to change lanes to win the game: .... .... .... .... start C... -> .C.. -> ..C. -> ...C .... .... .... ....

  2. {".......",".......","..#...."}

    Returns: 0

  3. {"....","....","...."}

    Returns: 0

  4. {".....",".....","....."}

    Returns: 0

  5. {"........","........","........"}

    Returns: 0

  6. {"...#......#..................",".......#................#....","......#...............#...#.."}

    Returns: 3

  7. {"........#..",".........#.","........#.."}

    Returns: 1

  8. {"..........","..........","..#.#....."}

    Returns: 0

  9. {".......#..","..........",".........."}

    Returns: 0

  10. {".........#...#.......",".#.........#..#......",".....#......#..#....."}

    Returns: 5

  11. {"..........","..#..#....",".......#.."}

    Returns: 1

  12. {".....#..","........","#......."}

    Returns: 0

  13. {".",".","."}

    Returns: 0

  14. {".#..","....","...."}

    Returns: 0

  15. {".......","..#....","......."}

    Returns: 1

  16. {"......","......","......"}

    Returns: 0

  17. {"..","..",".."}

    Returns: 0

  18. {"###",".##","###"}

    Returns: -1

  19. {"#.###.##", ".#.#.#.#", "###.###."}

    Returns: 7

    #.###.## #C###.## #.###.## #.###.## #.###.## #.###C## #.###.## #.###.## C#.#.#.# -> .#.#.#.# -> .#C#.#.# -> .#.#.#.# -> .#.#C#.# -> .#.#.#.# -> .#.#.#C# -> .#.#.#.# ###.###. ###.###. ###.###. ###C###. ###.###. ###.###. ###.###. ###.###C -> end

  20. {".........",".....#...","........."}

    Returns: 1

  21. {"..#.###","......#","...#..."}

    Returns: 1

  22. {"....#...#..#..#.#...",".......##..#...#....","#..#..#....#..##...."}

    Returns: -1

  23. {"..#....#..#.#...#..", "...#.#...#.#..#..#.", ".##..........#...#."}

    Returns: 5

  24. {"....#..#.",".........","........."}

    Returns: 0

  25. {".......",".#.....","...#..."}

    Returns: 1

  26. {"...#.......","........###",".#...#....."}

    Returns: 1

  27. {".#.............##",".................","........#..#....."}

    Returns: 0

  28. {"..##.#.#.#..###.......","..........#...........","...#...#..##....##..#."}

    Returns: 2

  29. {"..#....#..#.#....#.....#","...####...#..#.#...##...","#..#...#####.........#.."}

    Returns: -1

  30. {"...##.............#...","...#.#.....#....#.....",".##.....#....#.#....##"}

    Returns: 4

  31. {".........",".#.......","........."}

    Returns: 1

  32. {"#..#.#.##.", ".#.#...##.", ".###.##.#."}

    Returns: -1

    John can't reach the end of the road.

  33. {".#.#.#.#....####..##..","..###..#...#.##...#...","#.##...#......#.###.##"}

    Returns: -1

  34. {".###.#.#.........#.#.#..#....#....","........#.....##...#.........#.##.","......#..###..#..#..##....#......."}

    Returns: 5

  35. {"...#.........#","....#..#......",".#..##.....##."}

    Returns: 2

  36. {"#...#.....##....###..####..#",".####....#.##...#.###...#.#.",".#.#...#....#..######..##..."}

    Returns: -1

  37. {"#..##.#...##....#..###.","..##..#..###.#....#.#..","..##...#.#.##...##..#.#"}

    Returns: -1

  38. {".....#........#..","..#.#............","....#.......##.#."}

    Returns: 2

  39. {"#.#....#.....##","...#.#..#.##...","#...#.#..##..#."}

    Returns: 4

  40. {"...........................","...........................","..........................."}

    Returns: 0

  41. {"#.######...#.","..##.#.######","###.#.##.##.."}

    Returns: -1

  42. {"##.##.....###....#####...#..#######..#.###.##..","......#....#..#.#..#.#....#..###.....#.......#.","..##...###.....###.##.#.#.#..##.##.#...#.###..."}

    Returns: -1

  43. {"...",".#.","..#"}

    Returns: 1

  44. {"..#....",".....#.","#...#.."}

    Returns: 1

  45. {".#.#...#","....####","...##..#"}

    Returns: -1

  46. {"..#.##.#.#.#...###.##.#.######.#..####.#..####",".####.#.#.#####..##.#.####..###..##.#######.#.","#####.#.#####.###..#########.#####..###.#.####"}

    Returns: -1

  47. {"...........#","......#...#.",".....#.#.#.."}

    Returns: 2

  48. {"###..#.#...#....#.#...##......#..#.....","...#..#.....#.##.##..#....###...#.##...","....#.............#....#.#...#........."}

    Returns: -1

  49. {".#.#####.##","..######..#",".#....###.."}

    Returns: -1

  50. {"####.#..###.",".##..##..#.#","...##.##.#.#"}

    Returns: -1

  51. {"######.##########.####.##.#####.#.###.#.####.#####",".##.########.######..##.######.#..#..##..#########","#############.###.##.##########.#####.#######.####"}

    Returns: -1

  52. {"......................................#...........","....................#....#..............#.#.......",".................................................."}

    Returns: 1

  53. {"##.#####.######.####.######.#...#.########.##.#.##",".##..#########.###..######.#.###.###.#.##..#.#####","#..##....#...####..####.###.########...##..#.##.##"}

    Returns: -1

  54. {".#.#.#####.##.######.#.#...#.##.#...#..#.#########",".##.########...#######.####..##.#####.#..#.###..##","####..#.########..###.#.###.##...####.######.#####"}

    Returns: -1

  55. {"######.######################.##########.###.#####",".########################.###..#####.#############","#..##############.###########.######.#.###########"}

    Returns: -1

  56. {"#.###.###.###.###.###.###.###.###.###.###.###.###.",".#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..","###.###.###.###.###.###.###.###.###.###.###.###.#."}

    Returns: 48

  57. {"...#.....##......#..#.#.......",".......#......................",".....#........###...#....#...."}

    Returns: 2

  58. {"......#.......#....#.....#..........#........#.","..#...........#.........#................#.....","......................#........................"}

    Returns: 3

  59. {"....#.#..........#..#...##.......#.#..#",".....##.##.#.#..........#..##..........",".#...#.#......#..#..##......#.#.#..##.."}

    Returns: -1

  60. {".#.....#...#.##.#.#.........#.#.#...#.....#...#..",".....#..#..##.##.....####..#.##.#.#............##","....#...#...##........#.####.#...#....#.......###"}

    Returns: -1

  61. { "..#", ".##", "##." }

    Returns: -1

  62. {"............#.............#.......#......#.....#..", "....#...#.......#...#....#....#...........#....#..", "...............#........#.......#...#.....#......." }

    Returns: 9

  63. {".#.", ".#.", ".#." }

    Returns: -1

  64. {"..................................................", "..................................................", ".................................................." }

    Returns: 0

  65. {"..", ".#", ".#" }

    Returns: 1

  66. {"......#...........................................", "..................................................", ".................................................." }

    Returns: 0

  67. {"...", ".##", "###" }

    Returns: 1

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: