Statistics

Problem Statement for "EllysChessboard"

Problem Statement

Elly has a standard chessboard, divided into 8 by 8 unit square cells. She wants to place pebbles onto some of the cells. You are given a String[] board. The j-th character of the i-th element of board is '#' if she wants to put a pebble onto the cell (i, j), and it is '.' otherwise.

Initially the chessboard doesn't contain any pebbles. Elly places the pebbles one by one. The cost of adding a pebble is defined as follows. If this is the first pebble to be placed (i.e., the board is empty), it can be placed for free. Otherwise, the cost is the Manhattan distance (see Notes for the definition) to the most distant pebble that has already been placed on the board.

Return the minimal total cost of placing a pebble onto each chosen cell.

Definition

Class:
EllysChessboard
Method:
minCost
Parameters:
String[]
Returns:
int
Method signature:
int minCost(String[] board)
(be sure your method is public)

Notes

  • The Manhattan distance between the cell (x1, y1) and the cell (x2, y2) is defined as |x1-x2| + |y1-y2|, where || denotes absolute value.

Constraints

  • board will contain exactly 8 elements.
  • Each element of board will contain exactly 8 characters.
  • Each character in board will be either '#' or '.'.

Examples

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

    Returns: 10

    Elly wants to put pebbles on three cells: (2, 3), (3, 1), and (4, 7). One of the optimal ways to do this is as follows: First, put a pebble to (2, 3). It costs nothing. Next, put a pebble to (3, 1). It costs |2-3| + |3-1| = 3. Next, put a pebble to (4, 7). The Manhattan distance between (4, 7) and (2, 3) is 6, and the Manhattan distance between (4, 7) and (3, 1) is 7, so the cost is max(6, 7) = 7. The total cost is 0 + 3 + 7 = 10.

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

    Returns: 0

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

    Returns: 0

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

    Returns: 4

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

    Returns: 6

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

    Returns: 16

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

    Returns: 29

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

    Returns: 32

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

    Returns: 31

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

    Returns: 38

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

    Returns: 56

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

    Returns: 58

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

    Returns: 64

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

    Returns: 71

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

    Returns: 74

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

    Returns: 83

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

    Returns: 96

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

    Returns: 95

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

    Returns: 101

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

    Returns: 114

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

    Returns: 136

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

    Returns: 140

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

    Returns: 156

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

    Returns: 141

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

    Returns: 174

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

    Returns: 154

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

    Returns: 161

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

    Returns: 191

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

    Returns: 166

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

    Returns: 189

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

    Returns: 198

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

    Returns: 220

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

    Returns: 212

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

    Returns: 229

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

    Returns: 214

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

    Returns: 248

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

    Returns: 246

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

    Returns: 249

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

    Returns: 275

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

    Returns: 274

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

    Returns: 257

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

    Returns: 267

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

    Returns: 288

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

    Returns: 295

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

    Returns: 311

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

    Returns: 312

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

    Returns: 306

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

    Returns: 320

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

    Returns: 341

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

    Returns: 337

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

    Returns: 349

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

    Returns: 357

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

    Returns: 377

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

    Returns: 381

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

    Returns: 393

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

    Returns: 389

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

    Returns: 388

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

    Returns: 415

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

    Returns: 416

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

    Returns: 439

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

    Returns: 442

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

    Returns: 448

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

    Returns: 457

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

    Returns: 463

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

    Returns: 466

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

    Returns: 476

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

    Returns: 316

  68. {"........", "........", "........", "........", "........", "........", "........", "........" }

    Returns: 0

  69. {"####....", "####....", "####....", "####...#", "####..##", "####...#", "####....", "####...." }

    Returns: 217

  70. {"##.#.#..", "######.#", "#####.##", "#####..#", "#######.", "#####..#", "##..####", "#.#.####" }

    Returns: 349

  71. {"########", "########", "########", "###..###", "###..###", "########", "########", "########" }

    Returns: 459

  72. {"........", "#......#", "........", "........", "........", "........", "#......#", "#......#" }

    Returns: 43

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: