Connection Status:
Competition Arena > OneBlack

OneBlack

TCO13 Semifinal 2 · 2013-02-19 · by rng_58

TCO13 Semifinal 2 · 2013-02-19 · by rng_58 · Dynamic Programming, Graph Theory
Class Name: OneBlack
Return Type: int
Method Name: countColorings
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{"---",
 "---",
 "---"}
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.

1)
{"---",
 "-#-",
 "---"}
Returns: 11
2)
{"--#",
 "##-",
 "---"}
Returns: 64

There is no path, so all 2^6 colorings satisfy the condition.

3)
{"---------------#-----#----#---",
 "-------#----##----------------",
 "-#--------#--#-#--------------",
 "---------#--------------------",
 "----------###-------#--#-#----",
 "#------#--------#-#--#------#-",
 "-----------------#------------",
 "---------------#-----#-#--#---",
 "-------------#----------------",
 "------#--#--#---#----#--#-#---",
 "-----------------##-----------",
 "---#------------##------------",
 "-----------#--#---------------",
 "#---------#-------------------",
 "#---#---------#---#-----------",
 "-#-#--#------------#----#---#-",
 "----------------------#-----#-",
 "-----#-------------------#----",
 "-----#--##--#---------#---#---",
 "--#------##-#--#-------#--###-",
 "---------#----------------#---",
 "----------------#-------------",
 "--------------#------#-------#",
 "----------------------#-------",
 "-#-------------------#--------",
 "-#-#-#------#------------#----",
 "-------#----------------------",
 "#-------------#---#--#--------",
 "-----#-----#--------------##-#",
 "-------------#--------#-------"}
Returns: 96909591
4)
{"----",
 "-##-",
 "----"}
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.

Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OneBlack with a public method int countColorings(vector<string> grid) · 64 test cases · 2 s / 256 MB per case

Submitting as anonymous