Statistics

Problem Statement for "TurnOffLightsDiv1"

Problem Statement

Some people leave the lights on when they leave their workplaces. What a waste of resources! Lucyanna waits until all students and professors leave the university building, then goes and turns all the lights off.

Viewed from the side, the university building is a rectangle of cells with N rows and M columns. Each row represents one floor. On each floor, the leftmost cell and the rightmost cell contain stairs, and all other cells are rooms. Only rooms can have their lights turned on and off. Floors are numbered starting from 0 at the bottom. Cells on a floor are numbered starting from 0 on the left. (Thus, cells 0 and M-1 are always stairs.)

Lucyanna starts her quest in the cell (0,0). Her goal is to turn off all the lights and return to the cell (0,0).

In one move, Lucyanna can go from her cell to an adjacent cell in the same row. If her current cell contains stairs, she can also move one floor up or down, if there is another floor in that direction. Each movement takes one minute.

Lucyanna can only turn off the light in the room in which she currently stands. This also takes one minute per room.

You are given the String[] building. If building[r][c] = '#', the room with coordinates (r,c) has its light on. Otherwise, building[r][c] will be '.'. Calculate and return the minimum time in minutes for Lucyanna to turn off all the lights and return to the starting position.

Definition

Class:
TurnOffLightsDiv1
Method:
getMinimumTime
Parameters:
String[]
Returns:
int
Method signature:
int getMinimumTime(String[] building)
(be sure your method is public)

Notes

  • Lucyanna is not required to visit all cells.

Constraints

  • N will be between 1 and 9, inclusive.
  • M will be between 3 and 47, inclusive.
  • building will contain exactly N elements.
  • Each element of building will contain exactly M characters.
  • No element of building will contain characters other than '#' and '.'.
  • The first and the last character of each element of building will be '.'

Examples

  1. {".##."}

    Returns: 6

    One optimal solution: Move right, turn off the light, move right, turn off the light, move left, move left.

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

    Returns: 5

    The only optimal solution: Go one floor up, move right, turn off the light, move left, go one floor down. Note that element 0 of building represents the bottom floor where you start.

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

    Returns: 21

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

    Returns: 742

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

    Returns: 879

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

    Returns: 0

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

    Returns: 81

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

    Returns: 595

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

    Returns: 568

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

    Returns: 572

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

    Returns: 548

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

    Returns: 580

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

    Returns: 576

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

    Returns: 569

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

    Returns: 582

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

    Returns: 571

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

    Returns: 562

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

    Returns: 415

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

    Returns: 455

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

    Returns: 425

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

    Returns: 445

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

    Returns: 470

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

    Returns: 387

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

    Returns: 373

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

    Returns: 369

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

    Returns: 466

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

    Returns: 390

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

    Returns: 381

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

    Returns: 453

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

    Returns: 427

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

    Returns: 387

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

    Returns: 473

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

    Returns: 292

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

    Returns: 52

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

    Returns: 161

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

    Returns: 9

  37. {"........"}

    Returns: 0

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

    Returns: 589

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

    Returns: 76

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: