問題
게으른 관광객은 최대한 많은 관광지를 한 발짝의 낭비없이 방문하기를 원한다.
도시의 북서쪽 지역에 위치한 호텔에서 출발하여 도시의 남동쪽의 끝으로 간후 돌아오는 길을 택하는데,
남동쪽으로 갈 때는 남쪽 혹은 동쪽으로 만 가고 , 북서쪽으로 돌아올때는 북쪽 혹은 서쪽으로만 움직일 수 있다.
도시의 지도를 본 관광객은 길이 중간 중간에 막혀 있어 이러한 길을 알아내는 것이 그렇게 쉽지 않다는 것을 알았다.
그래서 당신에게 도움을 요청했다.
이차원 도시의 지도가 주어지고 관심 지역과 막힌 지역의 정보가 주어질 때 방문가능한 최대 관심 지역수를 출력한다.
入力
도시 지도는 2차원 배열의 형태로 주어진다.
입력의 첫 줄은 W, H(2≤W, H≤100) 가 주어진다.
W는 도시 지도의 폭이고, H은 지도의 높이이다.
다음 H 라인에는 W 개의 문자가 주어진다.
‘.’ : 갈수있는 지역
‘*’ : 관심 지역
‘#’ : 막힌 지역
<제한사항>
* 위 왼쪽( 출발지 ) 과 아래 오른쪽(터닝 포인트)은 반드시 도달 가능하다.
* 위 왼쪽( 출발지 ) 과 아래 오른쪽(터닝 포인트) 사이에는 H+W-2 크기의 갈수 있는 길이 존재
出力
방문가능한 최대 관심지역수를 출력한다.
例題 #1
9 7
*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........
7
例題 #2
5 5
.*.*.
*###.
*.*.*
.###*
.*.*.
8
出典
Svenskt Mästerskap i Programmering/Norgesmesterskapet 2004, poj 2964
ログインしないとコードを書けません。