OneBlack | Topcoder Archive

Problem Statement

Fox Ciel's room is divided into N times M unit cells. Each cell is either empty or a wall. The cells are numbered (0, 0) through (N-1, M-1).

You are given a String[] grid that describes Ciel's room. If the j-th character of the i-th element of grid is '#', cell (i, j) is a wall. Similarly, character '-' denotes an empty cell.

There is an entrance in the cell (0, 0) and an exit in the cell (N-1, M-1). From any cell (i, j) Ciel has at most two options how to move: she can move to the cell (i+1, j) or to the cell (i, j+1). Of course, she cannot step outside the room and she cannot step into a cell that contains a wall.

Cat Snuke wants to color each empty cell black or white. Additionally, the coloring must have the following property: Each of Ciel's valid paths from (0, 0) to (N-1, M-1) must contain exactly one black cell. Return the number of ways to color the cells, modulo 1,000,000,007.

Definition

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

Constraints

grid will contain between 2 and 30 elements, inclusive.
Each element of grid will contain between 2 and 30 characters, inclusive.
Each element of grid will contain the same number of characters.
Each character in grid will be either '#' or '-'.
The first character of the first element of grid and the last character of the last element of grid will be '-'.

Examples

```
{"---",
 "---",
 "---"}
```
```
Returns: 5
```
There are six valid paths Ciel may take: (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2) (0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2) (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) Each of these paths must contain exactly one black cell. There are five ways to do so: Color (0, 0) black. Color (0, 1) and (1, 0) black. Color (0, 2), (1, 1), and (2, 0) black. Color (1, 2) and (2, 1) black. Color (2, 2) black.
```
{"--#",
 "##-",
 "---"}
```
```
Returns: 64
```
There is no path, so all 2^6 colorings satisfy the condition.
```
{"----",
 "-##-",
 "----"}
```
```
Returns: 18
```
Color (0, 0) black. Color (2, 3) black. Color one of {(0, 1), (0, 2), (0, 3), (1, 3)} black, and color one of {(1, 0), (2, 0), (2, 1), (2, 2)} black. The total number of valid colorings is 1 + 1 + 4 * 4 = 18.

{"------##",
 "-##--#--",
 "---#----",
 "-----##-",
 "#-------"}

Returns: 432

{"------------------------------",
 "------------------------------",
 "------------------------------",
 "--#####------###-------###----",
 "----#-------#---#-----#---#---",
 "----#-------#---------#---#---",
 "----#-------#---------#---#---",
 "----#-------#---#-----#---#---",
 "----#--------###-------###----",
 "------------------------------",
 "------------------------------",
 "------#####--------#####------",
 "----------#--------#---#------",
 "----------#--------#---#------",
 "------#####--------#---#------",
 "------#------------#---#------",
 "------#------------#---#------",
 "------#####--------#####------",
 "------------------------------",
 "------------------------------",
 "--------#----------#####------",
 "--------#--------------#------",
 "--------#--------------#------",
 "--------#----------#####------",
 "--------#--------------#------",
 "--------#--------------#------",
 "--------#----------#####------",
 "------------------------------",
 "------------------------------",
 "------------------------------"}

Returns: 903122246

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.