Statistics

Problem Statement for "MatrixPainting"

Problem Statement

There is a matrix with 9 rows and 9 columns. Each cell of the matrix is either black or white. With a single repaint operation, you can repaint all the cells in a single row or column black if the row or column already contains at least 5 black cells. Your goal is to make all the cells in the matrix black using a minimal number of repaint operations.

You will be given a String[] matrix, where the jth character of the ith element represents the cell at row i, column j. Black cells will be written as '1' (one), and white cells will be written as '0' (zero). Return the minimal number of repaint operations required to make all the cells black, or -1 if this is impossible.

Definition

Class:
MatrixPainting
Method:
countRepaints
Parameters:
String[]
Returns:
int
Method signature:
int countRepaints(String[] matrix)
(be sure your method is public)

Constraints

  • matrix will contain exactly 9 elements.
  • Each element of matrix will contain exactly 9 characters.
  • Each element of matrix will consist of '0' and '1' characters only.

Examples

  1. {"001111111", "011111111", "011111111", "011111111", "011111111", "101111111", "101111111", "101111111", "101111111"}

    Returns: 3

    First, you should repaint the first row. After that, you can repaint the first and the second column.

  2. {"011111111", "101111111", "110111111", "111011111", "111101111", "111110111", "111111011", "111111101", "111111110"}

    Returns: 9

    Each white cell must be repainted separately.

  3. {"000000001", "000000011", "000000111", "000001111", "000011111", "000011110", "000011100", "000011000", "000010000"}

    Returns: 14

    After repainting the 5 rightmost columns, you will be able to repaint the rows.

  4. {"000000001", "000000011", "000000111", "000001111", "000011111", "000011110", "000011100", "000011000", "000000000"}

    Returns: -1

  5. {"011111111", "010001001", "111111101", "011111111", "101010100", "011111111", "111111101", "111011101", "011111111"}

    Returns: 5

  6. {"110101100","101100110","111011110","110111110","111011001","111010001","100111101","100110011","101001011"}

    Returns: 8

  7. {"000101111","110111011","111111101","101011011","101101100","111100001","110010110","010110110","111110000"}

    Returns: 9

  8. {"001011101","100011011","100111010","101111111","110101101","010101110","111000011","111111100","111001010"}

    Returns: 9

  9. {"101100101","110001011","011111111","110010110","111001001","010111111","110110001","011101100","011111011"}

    Returns: 9

  10. {"011111010","100111001","101100101","101000111","010010111","110111110","101010101","110011011","111111001"}

    Returns: 9

  11. {"111011011","001111111","110110001","100101101","011110010","001111100","100010111","011011001","110010110"}

    Returns: 9

  12. {"101011001","110110001","110100110","011011101","101001110","010100111","011011100","000111011","101100110"}

    Returns: 9

  13. {"011110110","111011100","110100101","010111001","110111111","101001011","101011001","101010110","101101010"}

    Returns: 9

  14. {"111101011","100111001","111010101","110101011","001010111","011011010","111100100","011011100","011100110"}

    Returns: 9

  15. {"110010011","111111111","011111000","110011101","011110100","110100110","100011011","011101001","011000111"}

    Returns: 8

  16. {"011111111","110111110","110011011","101111111","111001001","001111101","110111111","111011111","101111111"}

    Returns: 8

  17. {"111111111","011111111","111100101","110111111","101010110","111111110","111110110","111111111","111111110"}

    Returns: 6

  18. {"111111111","101010110","001111111","100101111","111011110","111110111","110011111","101110101","011111110"}

    Returns: 8

  19. {"111110101","110101111","011111100","111011011","111100111","111111101","010010111","111111111","011110110"}

    Returns: 8

  20. {"111111010","111111110","111111111","111011111","010111100","011101110","111011111","110111111","001111111"}

    Returns: 7

  21. {"101011111","111111111","111110111","010110101","111110110","111111111","111010110","001111101","111101111"}

    Returns: 7

  22. {"110110100","111111111","111011101","111111111","101100110","100111111","111111111","000111110","010111111"}

    Returns: 6

  23. {"101111101","111111111","111110101","110001011","010001111","101110111","101101111","111110111","111011110"}

    Returns: 7

  24. {"111111011","111111011","111110110","111110110","010111101","111111110","111101011","111111111","111110110"}

    Returns: 5

  25. {"111110111","100101111","111111110","111101011","111001111","111011100","111111111","010101111","111111111"}

    Returns: 7

  26. {"101101001","111000110","111100100","101001101","100010111","110110001","010111010","011011110","000111011"}

    Returns: 9

  27. {"100110101","011111100","001100111","101011001","011001011","100101011","011011010","110111100","110000111"}

    Returns: 9

  28. {"101101010","010010111","010101101","111011000","000111101","111010001","111000110","101111010","010100111"}

    Returns: 9

  29. {"100101110","011000111","010111001","011100110","010111110","101011010","101011001","110100101","101011001"}

    Returns: 9

  30. {"110100101","111110000","101001111","011110100","011001011","010111011","010111100","111000110","100011011"}

    Returns: 9

  31. {"111010111","100101011","101110100","110011001","011101010","000111110","011000111","001111001","111000101"}

    Returns: 9

  32. {"111001100","010011101","010111010","101101010","101100101","011000111","101010110","010110011","100111001"}

    Returns: 9

  33. {"001011011","010111001","110110100","111001100","100110110","111100110","101101001","100001111","011010011"}

    Returns: 9

  34. {"011001011","111100010","100111100","110010101","111100010","111101000","100011101","001110111","000011111"}

    Returns: 9

  35. {"110101010","100110101","101110100","001100111","001001111","111001001","010011110","111011010","010110101"}

    Returns: 9

  36. {"111111111","011111111","110011100","101110100","010111110","110101010","011101001","110101011","011101001"}

    Returns: 8

  37. {"100011101","011010111","110100011","001111100","101011010","111011111","010100111","100100111","011101111"}

    Returns: 9

  38. {"111100100","111111011","111000011","001111001","010111010","101100110","100001111","110011100","000110111"}

    Returns: 9

  39. {"101011110","111100001","100110101","110111011","111100011","110011100","111001010","100011110","101100101"}

    Returns: 8

  40. {"110001101","010110101","101110001","100111011","110001110","001111100","101001110","011000111","111111010"}

    Returns: 9

  41. {"010110011","111111100","111001001","101101111","101101100","101101110","011010110","110010101","100011011"}

    Returns: 9

  42. {"011010101","000111101","010111110","001010111","101001011","101101101","110110100","110001110","111100010"}

    Returns: 9

  43. {"011001110","011111100","100100111","011110001","010101011","111111110","101110011","110111000","111100101"}

    Returns: 9

  44. {"111001001","101111011","100010111","110100110","001011110","111110011","001111100","111100001","011001101"}

    Returns: 9

  45. {"111100100","011010011","000111111","010011110","011101001","111001010","100111111","100001111","101110010"}

    Returns: 9

  46. {"100011000","101000100","101000010","010101001","111111101","111000111","100010100","001010100","011101110"}

    Returns: 12

  47. {"101110001","111000000","100000100","110110010","000101000","001101001","000010000","001111010","110001010"}

    Returns: 13

  48. {"001010001","011100000","000110101","101010100","101100001","110101011","010000100","100010111","110001111"}

    Returns: 11

  49. {"001110110","110001011","011111010","011111010","010000010","110011010","100111001","000111001","001010000"}

    Returns: 11

  50. {"111011101","101100101","000000001","011011011","010101100","000001001","001101110","001101001","101011100"}

    Returns: 11

  51. {"011001010","001111000","111011100","010100001","001110100","001111000","110011011","000110001","011010110"}

    Returns: 11

  52. {"110010101","101111001","100101010","101001001","000011101","100011001","000101111","100001101","000001001"}

    Returns: 11

  53. {"100111111","100011101","001010111","000110111","000111000","101011000","100111010","010011111","111000111"}

    Returns: 10

  54. {"100011001","111010001","010001001","100010011","001100010","110011101","111100000","011111010","111100000"}

    Returns: 11

  55. {"110001110","000101011","010001010","111011011","111010010","001010000","110101111","010110110","011111101"}

    Returns: 10

  56. {"110111101","011101111","110111111","101111000","111111010","111010100","111111101","001111111","010111010"}

    Returns: 8

  57. {"111100111","111000101","001111011","110011110","011111010","011111110","110110011","111001111","111011111"}

    Returns: 9

  58. {"101111001","011001100","011111111","110101000","011111111","111101101","101111001","110101110","111111010"}

    Returns: 8

  59. {"111111111","110101110","111111110","001111111","010110111","111110001","101011111","111110101","110101100"}

    Returns: 8

  60. {"011001011","111110101","001111100","111111111","111101101","110111111","111011001","101111110","001111111"}

    Returns: 8

  61. {"011111111","111011111","101111110","011111111","111111010","111111101","111010011","111011111","111110111"}

    Returns: 7

  62. {"111111111","111111110","111111111","101110011","111110111","010111111","101101011","101110001","111101111"}

    Returns: 7

  63. {"111101111","111111011","000111110","101111101","011111111","011111110","110011110","001111101","110001111"}

    Returns: 8

  64. {"111111111","111010110","111111001","111101111","111011110","011101001","110111001","111111001","101110111"}

    Returns: 8

  65. {"110111111","111001011","111111100","000111111","111111101","110011111","011110111","111111011","110101011"}

    Returns: 8

  66. {"001111011","111010010","011111100","110011011","111110110","101011100","001000111","110111101","100110111"}

    Returns: 9

  67. {"101110111","001010110","010110111","010011011","001011101","011011101","101001011","010110001","010011111"}

    Returns: 10

  68. {"100011110","111110111","110111101","110101111","110101111","110110011","011001000","010001001","101100111"}

    Returns: 9

  69. {"101111011","110101111","101000110","011111111","010111010","111011101","101100101","101111101","011011111"}

    Returns: 9

  70. {"111111110","111011111","101111101","110010110","100010100","100110111","111100011","010011100","110101101"}

    Returns: 9

  71. {"101011111","101010010","111111111","100111001","011000000","110001110","111011111","110110111","000111001"}

    Returns: 10

  72. {"110111111","011110111","110001100","001001100","100100111","110100011","111011111","101111111","110011111"}

    Returns: 8

  73. {"110110010","111111010","101010011","011100111","100110011","011110111","101111111","110100111","011101101"}

    Returns: 9

  74. {"101011110","110001111","011001111","011101011","101100110","101111110","111111111","011000100","011111011"}

    Returns: 9

  75. {"100001011","100100000","100100111","110111111","110111111","001111001","011111000","011100001","111110011"}

    Returns: 9

  76. { "111111111", "111111111", "111111111", "111111111", "111111111", "111111111", "111111111", "111111111", "111111111" }

    Returns: 0

  77. { "111110000", "000011101", "100000001", "100000001", "010000011", "010001010", "000000010", "000010010", "111100000" }

    Returns: 14

  78. { "111110000", "000011101", "100000001", "100000001", "010010011", "010001010", "000000010", "000010010", "111100000" }

    Returns: 14

  79. { "000000000", "000000000", "000000000", "000000000", "000000000", "000000000", "000000000", "000000000", "000000000" }

    Returns: -1

  80. { "111110000", "000011101", "100010001", "100010001", "010010011", "010011010", "000010010", "000010010", "111100000" }

    Returns: 13

  81. { "111110000", "000011101", "100010001", "100010001", "011111111", "010011010", "000010010", "000010010", "111100000" }

    Returns: 12

  82. {"110101111","001101100","110110100","100011001","101100010","011101110","001101110","001010011","111010001"}

    Returns: 10

  83. {"101100010","011010000","110100011","001101110","111011101","100010001","010111110","010011011","010010101"}

    Returns: 11

  84. {"011110111","101001110","100101011","010011001","001101001","111011110","100010010","101000111","011100011"}

    Returns: 10

  85. {"100100011","111110110","101011101","110001011","000101101","111101100","010110011","001110100","000110011"}

    Returns: 10

  86. {"011011011","011101001","010010001","110001110","101100110","100110000","111000110","000110011","110111101"}

    Returns: 10

  87. {"010010011","101101010","100101010","110011111","101001011","010010001","001111101","111111100","010001111"}

    Returns: 10

  88. {"010011010","100111101","011101100","101000111","101001100","110010110","111011001","000101110","010100111"}

    Returns: 10

  89. {"011110110","100011100","001100001","010001011","010101111","001010101","110111000","101001011","110111110"}

    Returns: 10

  90. {"010101001","110110000","101011000","111001101","011000111","100101111","101011110","001011000","000111010"}

    Returns: 11

  91. {"111111100","101111010","001111101","010010111","011001001","100100011","010000010","111001100","110001001"}

    Returns: 10

  92. {"001101011","010101100","010100110","101111010","101100111","111011101","010110000","011000010","111010101"}

    Returns: 10

  93. {"100001110","011111010","110100010","001110101","011010011","111111111","100011110","010100101","110000001"}

    Returns: 10

  94. {"010001011","111010000","001110010","110011001","101100001","000101110","010100111","101111110","110001100"}

    Returns: 11

  95. {"110001000","100111010","101100000","001111001","011100101","100111111","110001111","111011110","101100100"}

    Returns: 10

  96. {"100001111","011001100","110111011","111100010","100101101","100101010","010010001","101111000","001011110"}

    Returns: 11

  97. {"011101110","101010100","111110011","110000100","011010101","010011101","111101110","110111101","010100110"}

    Returns: 9

  98. {"101010011","010101000","100111001","110110110","011001001","100110101","011101100","111001010","110000111"}

    Returns: 10

  99. {"110110111","111110010","011010101","101001110","011101101","000110000","110100001","010011011","100011011"}

    Returns: 10

  100. {"101111111","101100111","100000101","111111101","111000001","011011001","011001110","010111000","011001010"}

    Returns: 10

  101. {"110100001","101100011","101100011","001011110","000110110","000011100","111101100","011011001","110110111"}

    Returns: 10

  102. {"000011111", "010001001", "100111101", "011010011", "100000100", "011010111", "110101101", "111011101", "011111000" }

    Returns: 11

  103. {"111111111", "111111111", "111111111", "111111111", "111111111", "011110111", "011111011", "011111101", "011111110" }

    Returns: 4

  104. {"011101110", "011101110", "011101110", "011101110", "011111110", "011111110", "011111110", "011111110", "111111111" }

    Returns: 6

  105. {"111110000", "011111000", "001111100", "000111110", "000011111", "111110000", "011111000", "001111100", "000111110" }

    Returns: 9

  106. {"111110000", "111110111", "111110111", "111111011", "111111011", "111111101", "111111101", "111111110", "111111110" }

    Returns: 4

  107. {"000011111", "011111111", "011111111", "101111111", "101111111", "110111111", "110111111", "111011111", "111011111" }

    Returns: 4

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: