USACO 2005, poj 3051- 위성사진 > 문제은행 : 정보올림피아드&알고리즘




1131 : 위성사진

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
51 회   
시도횟수
133 회   

문제

농부 창호는 자신의 농장을 위성을 이용해 찍은 사진을 얻게 되었다. 

이 사진은 W*H 크기의 픽셀로 이루어진 사진이다. 

창호는 이렇게 찍힌 사진들 중에서 가장 많이 연속되어 연결된 목장의 크기가 알고 싶어 한다. 

목장이란 사진에 비어있지 않은 곳을 가정하며, 하나의 픽셀은 하나의 목장이 될 수 있다. 

연결된 목장이란 다른 목장과 가로 혹은 세로방향으로 맞닿아 있는 것을 뜻한다. 

또한 연속되어 연결 되었다는 것은 연결되었다고 가정한 목장들의 집합 안 에서 모든 두 지점에 대해, 

상하좌우로 목장만을 이동경로로 둘 경우 모든 두 지점에 대한 경로가 존재할 경우 이 집합 안의 목장들은 연속되어 연결 되었다고 이야기 한다.


각 위성사진은 2개의 문자로 이루어져 있는데 '*' 표시는 목장, '.' 은 비어있는 곳을 의미한다. 

아래는 이러한 위성사진의 예이다.


 


 

 

 


위의 그림에서 4, 16, 6개의 픽셀로 이루어진 연속된 목장이 존재한다. 

그리고 이 경우는 16이 창호가 찾고자 하는 답이 된다.

 


입력형식

첫 번째 줄에는 W와 H가 공백을 사이에 두고 입력 된다 (1≤W≤80, 1≤H≤1,000).
그 다음 줄부터 H의 줄에 W개의 문자 '*', '.'로 이루어진 위성 사진의 한 줄이 입력된다.


출력형식

입력된 위성사진에서 나타나는 가장 많은 연속된 목장의 개수를 출력한다.


입력 예

10 5 
..*.....**
.**..*****
.*...*....
..****.***
..****.***

출력 예

16


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP