dk6781_lee   1년 전

제목)

얇은 얼음 건너기

문제)
겨울의 추운 어느 날, JOI타로 군은 광장에 얇게 언 얼음을 깨며 놀기로 했다.
광장은 직사각형이며, 동서 방향으로 mmm개, 남북 방향으로 nnn개, 즉 m×nm \times nm×n 개의 구역으로 나누어져 있다.
또한, 얼음이 있는 구역과 없는 구역이 존재한다.

JOI타로 군은 다음 규칙에 따라 얼음을 깨며 구역을 이동하기로 했다.

  1. 얼음이 있는 어느 구역에서든 얼음 깨기를 시작할 수 있다.
  2. 동서남북 중 한 방향으로 인접한, 아직 깨지지 않은 얼음이 있는 구역으로 이동할 수 있다.
  3. 이동한 구역의 얼음은 반드시 깬다.

JOI타로 군이 얼음을 깨면서 이동할 수 있는 구역 수의 최댓값을 구하는 프로그램을 작성하라.
단, 1≤m≤901 \leq m \leq 901≤m≤90, 1≤n≤901 \leq n \leq 901≤n≤90 이다.
주어진 입력 데이터에서 이동 방법은 20만 가지를 초과하지 않는다.

입력)

입력은 n+2n+2n+2줄로 구성된다.
1번째 줄에는 정수 mmm이 주어진다.
2번째 줄에는 정수 nnn이 주어진다.
3번째 줄부터 n+2n+2n+2번째 줄까지 각 줄에는 0 또는 1이 공백으로 구분되어 mmm개씩 주어진다.
각 값은 해당 구역에 얇은 얼음이 있는지 여부를 나타낸다.

북쪽에서 iii번째, 서쪽에서 jjj번째 구역을 (i,j)(i, j)(i,j)로 표현한다고 하면 (1≤i≤n,1≤j≤m)(1 \leq i \leq n, 1 \leq j \leq m)(1≤i≤n,1≤j≤m),
i+2i+2i+2번째 줄의 jjj번째 값이 1이면 구역 (i,j)(i, j)(i,j)에 얼음이 존재함을 의미하고,
0이면 구역 (i,j)(i, j)(i,j)에 얼음이 없음을 의미한다.

출력)

이동할 수 있는 구역 수의 최댓값을 출력하시오.

예제 입력 1) 설명

입력 예제 1에 대해, 최댓값을 주는 이동 방법의 예시

예제 입력2) 설명
입력 예제 2에 대해, 최댓값을 주는 이동 방법의 예시
입력 예제 2에 대해, 최댓값을 주지 않는 이동 방법의 예시

댓글을 작성하려면 로그인해야 합니다.