이진수 격자

시간 제한1초메모리 제한1024 MB

요약

왼쪽 위에서 오른쪽 아래로 오른쪽이나 아래로만 이동하며 읽는 길이 2N-1의 이진수를 최대로 만드는 경로를 찾는다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 완전 탐색
정답자: 아직 제출이 없습니다

문제

각 칸에 $0$ 또는 $1$ 이 적혀 있는 $N \times N$ 격자가 있다. 인선이는 $1$ 행 $1$ 열에서 출발해 $N$ 행 $N$ 열까지 이동하는데, 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다. 인선이는 어떤 칸에 방문할 때마다 그 칸에 적힌 문자를 자신이 갖고 있는 문자열의 뒷부분에 덧붙인다. 예를 들어, 주어진 그림에서 인선이가 $1$ 행 $1$ 열에서 출발하여 순서대로 오른쪽, 아래, 오른쪽으로 한 칸씩 이동한다면 인선이가 가진 문자열은 1101이다.

$N$ 행 $N$ 열에 도착하면 인선이는 자신이 갖고 있는 문자열을 이진수로 해석한 값 $M$ 을 계산한다. 예를 들어, 인선이가 가진 문자열이 1101일 경우 $M=13$ 이다. 인선이가 계산하게 될 $M$ 의 최댓값을 구하시오.

입력

첫째 줄에 격자의 크기를 의미하는 정수 $N$ 이 주어진다. $(2 \leq N \leq 30)$

둘째 줄부터 $N$ 개의 줄에 걸쳐 한 줄에 $N$ 개의 정수가 공백으로 구분되어 주어진다. 이 정수는 반드시 $0$ 또는 $1$ 이다. $(i+1)$ 번째 줄에 주어진 $j$ 번째 수는 $i$ 행 $j$ 열에 적힌 격자의 칸에 적힌 수를 의미한다.

출력

$M$ 의 최댓값을 출력한다. 정답이 32비트 정수 범위를 넘을 수 있음에 주의하시오.

예제3

예제 1
입력
```
3
1 0 1
0 0 0
0 1 0
```
예상 출력
```
20
```
예제 2
입력
```
2
1 0
0 1
```
예상 출력
```
5
```

예제 3

입력

예상 출력