16999번 - Monotony 다국어

You are given an r×c grid. Each cell of this grid is filled with a number between 1 and r·c inclusive, and each cell’s number is distinct.

Define a grid of numbers to be monotonic if each row and column is either increasing or decreasing (this can be different for each row or column).

Define a subgrid of the grid as follows: First choose some nonempty subset of the rows and columns. Next, take elements that lie in both the chosen rows and columns in the same order.

There are (2^r−1)(2^c−1) nonempty subgrids of the given grid.Of these subgrids, count how many are monotonic.

Consider this grid:

1 2 5
7 6 4
9 8 3

There are nine 1×1 subgrids, nine 1×2’s, three 1×3’s, nine 2×1’s, nine 2×2’s, three 2×3’s, three 3×1’s, three 3×2’s, and one 3×3. They are all monotonic, for 9+9+3+9+9+3+3+3+1 = 49 monotonic subgrids.

Each test case will begin with a line with two space-separated integers r and c (1 ≤ r, c ≤ 20), which are the dimensions of the grid.

Each of the next r lines will contain c space-separated integers x (1 ≤ x ≤ r·c, all x’s are unique). This is the grid.

Output a single integer, which is the number of monotonic subgrids in the given grid.