래프팅 여행

면접 대비

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

요약

격자에 강의 흐름 방향과 관광지가 주어질 때, 뗏목이 출발한 칸부터 이동하면서 인접한 서로 다른 관광지를 가장 많이 방문하는 시작 칸을 찾습니다.

난이도: 보통10점 중 6점
유형: 그래프, DFS, 행렬
정답자: 아직 제출이 없습니다

문제

래프팅 여행을 계획하고 있다. 지형은 격자로 볼 수 있다. 각 칸은 육지이거나, 북, 남, 동, 서 중 한 방향으로 흐르는 강의 일부를 담고 있다. 일부 육지 칸에는 관광 명소가 있다.

강 칸 중 아무 곳이나 래프팅의 출발 지점으로 고를 수 있다. 뗏목이 강 칸(출발 칸 포함)에 도착하면, 그 칸의 물살 방향을 따라 인접한 칸으로 이동하거나 격자 밖으로 나간다.

뗏목이 관광 명소에 인접한 강 칸에 도달하면 그 명소를 방문할 수 있다. 출발 칸도 포함한다. (인접은 가로와 세로로 맞닿은 칸을 뜻하며, 대각선으로 맞닿은 칸은 포함하지 않는다.) 각 관광 명소는 최대 한 번만 방문할 수 있다.

뗏목이 육지 칸으로 올라가거나, 격자 밖으로 나가거나, 이전에 지나간 강 칸으로 다시 들어가면 래프팅이 멈춘다. 뗏목이 육지 칸에서 끝나면, 그 육지 칸에 인접한 관광 명소는 방문할 수 없다.

출발 칸을 최적으로 골랐을 때, 한 번의 래프팅에서 방문할 수 있는 관광 명소의 최대 개수는 얼마인가?

입력

입력의 첫 줄에는 정수 $r$ 과 $c$ 가 주어진다 ( $2 \leq r, c \leq 500$ ). 지형 격자는 $r$ 개의 행과 $c$ 개의 열로 이루어진다.

다음 $r$ 개의 줄에는 격자의 한 행을 나타내는 문자 $c$ 개가 각각 주어진다. '.'은 관광 명소가 없는 육지 칸이다. '#'은 관광 명소가 있는 육지 칸이다. 강 칸은 '^'(북), 'v'(남), '>'(동), '<'(서)로 표시된다. 격자에는 강 칸이 적어도 하나 있다.

출력

한 줄에 정수 하나를 출력한다. 이는 한 번의 래프팅에서 방문할 수 있는 관광 명소의 최대 개수다.

힌트

첫 번째 예제의 그림이다. 최적의 래프팅은 뗏목이 있는 칸에서 출발하며, 관광 명소 4곳(쌍안경으로 표시)을 방문한다. 여행 중 지나간 강 칸은 진한 파란색으로 표시되어 있다.

예제2

예제 1

입력

5 6
v<<<#v
v#v<.>
>>v<<<
..v##^
#<<<.^

예상 출력

예제 2
입력
```
4 5
>v<<.
^<..#
#...#
.#>^#
```
예상 출력
```
2
```