아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

엉겅퀴 다크워터

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

요약
물, 땅, 음식으로 이루어진 육각 격자에서 중앙 배가 바다로 도달할 수 있는 물과 맞닿은 연결된 땅 덩어리 중 음식 합이 가장 큰 것을 찾는다.
난이도

보통10점 중 7점

유형
BFS, DFS, 그래프, 구현
정답자
아직 제출이 없습니다

문제

엉겅퀴 '은안' 다크워터는 유명한 탐험가다. 칠해를 오래 항해한 끝에 그녀는 신비로운 군도, 침몰선 제도에 도착했다. 그곳의 지형은 고향 스코틀랜드와 크게 다르지 않다. 섬, 만, 드러난 바위, 좁은 물길, 작은 섬, 호수, 강섬, 암초, 산호초 등등. 그냥 거대한 미로일 뿐이다. 긴 여정 끝에 엉겅퀴와 선원들은 지쳐 있다. 이들은 상륙할 땅 하나를 골라 신선한 식량을 채우고 마땅히 누릴 휴식을 갖기로 합의한다. 망대에서 바라본 선원들은 배 주변 지형의 지도를 만들어 두었다. 엉겅퀴는 식량이 많은 땅에 닿고 싶어 한다. 선원들이 길고 넉넉하게 쉴 수 있도록. 물론 현재 위치에서 바다로 갈 수 있는 땅만 고를 수 있다.

정찰병들은 육각 격자의 점들에 위치한 여러 지점의 물, 땅, 식량을 지도에 표시했다. 그들이 볼 수 있는 범위는 배를 중심으로 한 육각형 영역이다. 따라서 지도의 각 지점에는 최대 여섯 개의 이웃이 있다. 배는 격자의 중심에 있고 항상 물 위에 있다.

엉겅퀴가 바다로 갈 수 있는 연결된 땅 중 식량이 가장 많은 곳을 찾도록 도와줄 수 있는가?

입력

입력 파일은 여러 테스트 케이스로 이루어진다. 입력 파일의 첫 줄에는 테스트 케이스의 수 nn이 주어진다. 각 테스트 케이스가 이어진다. 테스트 케이스의 첫 줄에는 영역을 나타내는 육각형의 한 변의 크기 dd (1≤d≤1001 \le d \le 100)가 주어진다. 다음 2d−12d-1개 줄이 영역을 나타낸다. 각 줄은 4d−34d-3개 문자로 이루어진다. kk번째 줄 (1≤k≤2d−11\le k \le 2d-1)은 2d−1−∣k−d∣2d-1 - |k-d|개의 글자를 한 칸씩 띄워 쓰고 줄 가운데에 맞춰 정렬한 것이다. 각 글자는 WW (물), LL (식량이 없는 땅), FF (식량이 있는 땅) 중 하나다. 가운데 줄의 가운데 글자는 항상 WW다.

출력

입력의 각 테스트 케이스마다, 엉겅퀴의 배가 처음 위치에서 바다로 갈 수 있는 연결된 땅 하나에 있는 식량의 최대 개수를 나타내는 정수 하나를 한 줄에 출력한다.

힌트

이미지 저작권

예제1

  1. 예제 1

    입력
    2
2
 W L 
F W F
 W W 
4
   W F L W   
  W W L W W  
 L F W W W L 
W W L W L L L
 F W F W W L 
  F W L W L  
   F W L W
    예상 출력
    1
2