#P1817. Connected Grid Coloring
Connected Grid Coloring
Connected Grid Coloring
Given an \(N \times M\) grid, each cell can be colored black or white. The constraints are:
- All black cells form a connected region, i.e. for any two black cells there is a path from one to the other moving only up, down, left, or right through black cells.
- All white cells form a connected region (under the same connectivity definition).
- At least one black cell must lie on the boundary of the grid.
- At least one white cell must lie on the boundary of the grid.
Your task is to calculate the number of valid colorings of the grid that satisfy the above conditions.
Note: A configuration where all cells are of the same color is invalid. The grid cells are indexed from 0 such that a cell is on the boundary if it is in the first row, last row, first column, or last column.
inputFormat
The input consists of a single line containing two integers \(N\) and \(M\) (the number of rows and columns of the grid, respectively).
outputFormat
Output a single integer, representing the number of valid ways to color the grid.
sample
1 1
0