LuckyGrid | Topcoder Archive

Problem Statement

Cat has decided to play a new pen-and-paper game on a grid. For the purpose of this game, a lucky number is any number in which each digit is either a 4 or a 7.

The game is played on a square grid. At the beginning of the game the player is presented with a partially filled grid: some of the cells contain the number 4, some contain the number 7, and all other cells are empty. The player must put either a 4 or a 7 into each of the empty cells. The player wins the game if she is able to fill in the empty cells in such a way that the sum of each row and also the sum of each column is a lucky number.

You are given a String[] grid representing the grid at the beginning of the game. Characters '4' and '7' represent filled cells, character '.' (period) represents an empty cell.

If the player cannot win the game, return -1. If she can win the game, find and return the smallest possible sum of the grid at the end of a won game.

Definition

Class:: LuckyGrid
Method:: findMinimumSum
Parameters:: String[]
Returns:: int
Method signature:: int findMinimumSum(String[] grid)
(be sure your method is public)

Constraints

Let n be a number between 1 and 68, inclusive.
grid will contain exactly n elements.
Each element of grid will contain exactly n characters.
Each character of each element of grid will be '4', '7', or '.'.

Examples

```
{"."}
```
```
Returns: 4
```
There are two ways to play this game: Either we put a 4 into the empty cell, or we put a 7 into the empty cell. In both cases we win the game. The answer is 4, because 4 is less than 7.
```
{"7"}
```
```
Returns: 7
```

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

Returns: 352

```
{".4.",
 "7.7",
 "4.."}
```
```
Returns: -1
```
The sum of the leftmost column will be either 4+7+4 = 15 or 7+7+4 = 18. Neither of these numbers is lucky.

{"774777..",
 "..4.....",
 "..7774..",
 "..7..7..",
 "..7..7..",
 "..7..74.",
 "..4..4..",
 "........"}

Returns: 355

{".44.....7..",
 ".44........",
 "...........",
 "...........",
 ".7.........",
 "...........",
 "...........",
 "...........",
 "...........",
 "...........",
 "..........."}

Returns: 490

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

Returns: 814

{"..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 ".............477747774....77777.....477774........................",
 ".................4.......4.........4......4.......................",
 ".................4......4.........4........4......................",
 ".................7......7.........7........7......................",
 ".................4......4.........4........4......................",
 ".................4.......4.........4......4.......................",
 ".................7........77777.....777777........................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................", 
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 "..................................................................",
 ".................................................................."}

Returns: 29304

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.