Monotony

면접 대비

시간 제한5초메모리 제한512 MB

요약

행과 열의 공집합이 아닌 모든 부분집합을 살펴보고, 각 행과 열이 증가하거나 감소하는 부분 격자의 개수를 센다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 시뮬레이션, 구현, 조합론
정답자: 아직 제출이 없습니다

문제

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 (2r−1)(2c−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.

예제2

예제 1
입력
```
3 3
1 2 5
7 6 4
9 8 3
```
예상 출력
```
49
```
예제 2
입력
```
4 3
8 2 5
12 9 6
3 1 10
11 7 4
```
예상 출력
```
64
```