Niuniu likes his maze and he wants to collect more mazes. Given n, m, a maze is a n x m grid. The rows and columns are numbered from 0. Let's call the cell on the i-th row and the j-th column as (i,j). There may be vertical walls between and . There may be horizontal walls between and . Two array v and h are given. The size of v is n x . If v[i][j] is 1, then there is a wall between and . If v[i][j] is 0, then there are two possibilities. There may or may not be a wall between and . The size of h is (n-1) x m. If h[i][j] is 1, then there is a wall between and . If h[i][j] is 0, then there are two possibilities. There may or may not be a wall between and . The beauty is defined as follows: Calculate the size of each connected component, the sum of their square is the beauty. You need output the sum of beauty of all possibilities. As the answer might be very large, you only need to output the answer mod 1000000007.
Niuniu likes his maze (Mei Zi) and he wants to collect more mazes. Given n, m, a maze is a n x m grid. The rows and columns are numbered from 0. Let's call the cell on the i-th row and the j-th column as (i,j). There may be vertical walls between (i, j) and (i, j + 1). There may be horizontal walls between (i, j) and (i + 1, j). Two array v and h are given. The size of v is n x (m - 1). If v[i][j] is 1, then there is a wall between (i, j) and (i, j + 1). If v[i][j] is 0, then there are two possibilities. There may or may not be a wall between (i, j) and (i, j + 1). The size of h is (n-1) x m. If h[i][j] is 1, then there is a wall between (i, j) and (i + 1, j). If h[i][j] is 0, then there are two possibilities. There may or may not be a wall between (i, j) and (i + 1, j). The beauty is defined as follows: Calculate the size of each connected component, the sum of their square is the beauty. You need output the sum of beauty of all possibilities. (Obviously, the number of possibilities are 2^{the number of 0 in v and h}) As the answer might be very large, you only need to output the answer mod 1000000007.
标签： HBC17708Maze题解
