24274번 - 구불구불 경주 트랙 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 24 | 16 | 15 | 75.000% |
문제
다오와 디지니는 새로운 카트라이더 경주 트랙을 만들고 있다. 경주 트랙은 $H\times W$ 크기의 빈 직사각형 격자판에 $1\times 1$ 크기의 정사각형 타일을 놓는 방식으로 만들어진다. 타일은 길이 그려져 있는 방향에 따라 다음 6가지로 나뉘며, 각각의 타일은 회전해서 놓을 수 있다.
모든 격자칸을 타일로 채우면 경주 트랙이 완성된다. 한 격자판에 여러 개의 경주 트랙을 만들 수도 있기 때문에, 완성된 격자판에서 임의의 두 칸을 잇는 길이 존재하지 않아도 된다. 타일을 배치할 때는 길의 끝이 다른 길의 끝과 이어져 있도록 배치해야 한다. 즉, 길의 끝이 격자판 밖을 향하거나, 이웃한 타일의 길과 이어져 있지 않으면 안 된다.
다오와 디지니는 먼저 타일을 배치할 구역을 나누었다. 다오의 구역에는 다오만 타일을 놓을 수 있고, 디지니의 구역에는 디지니만 타일을 놓을 수 있다. 나머지 칸에는 둘 중 아무나 타일을 놓을 수 있다.
6가지 타일을 사용해서 격자판을 꾸미려는 디지니와 다르게, 다오는 구불구불한 경주 트랙을 좋아해서 ㄱ자 형태로 굽은 길 타일만 사용하기로 했다. 또, 다오는 욕심이 많아서 자기가 놓는 타일의 개수를 최대화하고 싶다. 다오는 자신만의 미적 감각에 따라 타일 몇 개를 먼저 배치했지만, 자기가 놓을 타일의 개수를 최대화하기 위해 나머지 칸을 어떻게 채워야 하는지는 알아낼 수 없었다. 다오가 놓을 수 있는 타일의 최대 개수를 계산해서 다오를 도와주자! (단, 다오가 먼저 배치한 타일도 세어야 한다.)
입력
첫 번째 줄에는 격자판의 세로를 나타내는 $H$와 가로를 나타내는 $W$가 주어진다. $(1 \leq H, W \leq 100)$
두 번째 줄부터 $H$개의 줄만큼 격자판의 정보가 주어진다. 각 줄은 $W$개의 문자로 이루어져 있으며, 각 문자가 나타내는 것은 다음과 같다.
1: 왼쪽 칸과 위 칸을 잇는 길 타일2: 왼쪽 칸과 아래 칸을 잇는 길 타일3: 오른쪽 칸과 위 칸을 잇는 길 타일4: 오른쪽 칸과 아래 칸을 잇는 길 타일o: 다오만 타일을 놓을 수 있는 칸x: 디지니만 타일을 놓을 수 있는 칸.: 둘 중 아무나 타일을 놓을 수 있는 칸
1, 2, 3, 4가 나타내는 타일은 다오가 놓은 타일이다.
출력
다오가 먼저 배치한 타일을 포함하여, 다오가 놓을 수 있는 타일의 최대 개수를 출력한다. 만약 조건을 만족하도록 격자판을 채울 수 없거나, 다오가 먼저 배치한 타일이 조건에 어긋나면 -1을 출력한다.
예제 입력 1
4 5 4...x .2..2 .o1x. 3..3o
예제 출력 1
12
예제 1에 주어진 격자판은 다음과 같다. 파란색 칸은 다오의 구역, 노란색 칸은 디지니의 구역이다.
다음은 다오가 놓는 타일의 개수를 최대화하는 배치의 예시이다. 다오가 배치한 타일은 파란색, 디지니가 배치한 타일은 노란색으로 표시했다.
예제 입력 2
2 3 4o2 3x1
예제 출력 2
-1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호