You are given a board with N row and M columns. We will use (i,j) to denote the j-th cell in the i-th row (0-based indices). Each cell is initially white. You goal is to have a board that has at least one black cell in each row, and at the same time at least one black cell in each column.
You will paint the cells black in turns. In each turn, you select one cell (in a specific way that is given below) and color it black. You stop as soon as your goal is achieved.
You are given a String[] **prob** consisting of N elements, each M characters long. All characters in **prob** are digits ('0'-'9'). The digit represented by the j-th character in the i-th row (0-based indices) will be denoted p[i][j]. This digit is the relative probability of cell (i,j) being chosen in each turn.
Formally, let s be the sum of all p[i][j]. Then in each turn the cell (i,j) is chosen with probability p[i][j]/s. Note that the same cell may be chosen multiple times: we may sometimes choose a cell that is already black.
The constraints guarantee that achieving your goal is possible. Return the expected number of turns until your goal is achieved. |