Statistics

Problem Statement for "TopCraft"

Problem Statement

703 Gaming, inc. has released a new game called TopCraft. In this game, an army of coding professionals must attack the evil bugs infesting the world. These coding professionals (referred to in game terminology as "units") are classified as either division 1 or division 2 units.

In order to control units, the player must drag a selection rectangle across the screen. Any units encompassed by the rectangle get selected for control.

Stan Ford has just bought this game to kill time. Now he's stuck in a position where he has to attack the evil bugs as fast as he can. To accomplish this, he wants to select all of the division 1 units on his screen with as few selection rectangles as possible, but without selecting any division 2 units in the process. Write a method that, given the screen configuration, returns the minimum number of selection rectangles necessary to select all of the division 1 units.

The screen will be represented by a String[] with 10 elements, each of length 10. Each character will be either a '.' for a clear space, a '1' for a division 1 unit, or a '2' for a division 2 unit.

Definition

Class:
TopCraft
Method:
select
Parameters:
String[]
Returns:
int
Method signature:
int select(String[] select)
(be sure your method is public)

Notes

  • The same division 1 unit may be selected multiple times, if that leads to the least number of selection rectangles.

Constraints

  • units will contain 10 elements exactly.
  • each element of units will be 10 characters in length, exactly.
  • each element of units will be composed of the three characters '.', '1', and '2'.
  • there will be at least one occurence of '1' and at least one occurence of '2' in units.
  • there will be no more than 20 total combined units.

Examples

  1. {".........." ,".........." ,".........." ,".1.1.1...." ,".........." ,".1.1.1...." ,".......2.." ,".1.1.1...." ,"........1." ,".........."}

    Returns: 2

    A selection rectangle can be drawn around the block of 9 1s, and then another one around only the isolated 1: .......... .......... |-----|... |1.1.1|... |.....|... |1.1.1|... |.....|2.. |1.1.1||-| |-----||1| .......|-|

  2. {".........." ,".........." ,".........." ,"..111....." ,"..121....." ,"..111....." ,".........." ,".........." ,".........." ,".........."}

    Returns: 4

  3. {".........." ,".1....1..." ,"..2......." ,"...1.1...." ,"....2....1" ,".....1..2." ,"..1......." ,".......1.." ,".2........" ,"....111..."}

    Returns: 4

  4. {"1.........",".2......1.","..1....2..","...2..1...","....1.....",".....1....","...1..2...","..2....1..","........2.",".........1"}

    Returns: 7

  5. {".........1","..........","..........","....1.....","...121....","..12121...","...121....","....1.....","..........","1........."}

    Returns: 9

  6. {"........1.","........21","..........","..........","...121....","...212....","...121....","..........","12........",".1........"}

    Returns: 9

  7. {".1......1.","12......21","..........","..........","....2.....","...2.2....","..........","..........","12......21",".1......1."}

    Returns: 4

  8. {"........1.","1.......2.","..........","..........","...121....","...2.2....","...121....","..........",".2......21",".1........"}

    Returns: 7

  9. {"1212121...",".12121....","..121.....","..........","..........","..........","..........","..........","..........",".........."}

    Returns: 9

  10. {".........1","........12",".......1..","......12..",".....1....","....12....","...1......","..12......",".1........","12........"}

    Returns: 6

  11. {"..........",".1.......1","....1...2.","...2...1..","..1...2...",".....1....","....2...1.","...1...2..","......1...",".........1"}

    Returns: 5

  12. {"..2.......",".1.1......","2.2.......",".1...2....","....1.....","...2...1..","......2.2.",".....1.1..","......2...",".........."}

    Returns: 4

  13. {"..........","....21....","...21.....","..21......",".21.......",".1.....1..","......12..",".....12...",".....2....",".........."}

    Returns: 5

  14. {"..........","....21....","...21.....","..21......","..1.....1.",".......12.","......12..",".....12...","..........",".........1"}

    Returns: 5

  15. {"..........",".2.2.2.2.2","..........","..2.2.2.2.","..........","...2.1.2..","..........","....2.2...","..........",".....2...."}

    Returns: 1

  16. {"..........",".1.1.1.1.1","..........","..1.1.1.1.","..........","...1.2.1..","..........","....1.1...","..........",".....1...."}

    Returns: 4

  17. {"1.........","...21.....","..21......",".21.......",".1........","..........","......12..",".....12...","....12....",".........1"}

    Returns: 6

  18. {".....1...2",".....21...","......21..",".......21.","........21","..........","..1.......","..21......","..........","...21....."}

    Returns: 8

  19. {"...2..1..2","......21..",".......21.","........21","12........","..1.......","....1.....",".....2....",".....1....",".........."}

    Returns: 7

  20. {"..........", "21.......1", "1...1...2.", "...2...1..", "..1...2...", ".....1...1", "....2...1.", "...1...2..", "..2...1...", ".1.......1" }

    Returns: 6

  21. {"..........",".1.......1","....1...2.","...2...1..","..1...2...",".....1....", "1..12...1.","...1...2..","..2...1.1.",".1.......1"}

    Returns: 6

  22. {"......1.12",".....121.1","......121.",".......121","........12","..1......1", "...2......",".....1....",".1........",".........."}

    Returns: 10

  23. { "....12....", ".....12...", "......12..", ".......12.", "........12", "1........1", "21........", ".21.......", "..21......", "...21....."}

    Returns: 6

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: