상가 스탬프 투어
문제
한 상가 건물의 가게들이 R개의 행과 C개의 열로 반듯하게 나뉘어 있다. 각 칸에는 가게가 하나씩 들어 있고, 가게마다 업종을 나타내는 알파벳 대문자가 하나씩 적혀 있다. 업종이 같은 가게는 건물 안 여러 곳에 있을 수 있다.
이 상가에서는 스탬프 투어 행사를 한다. 참가자는 1행 1열의 가게에서 출발해 거기서 스탬프를 하나 받는다. 그다음부터는 지금 서 있는 가게와 행 방향이나 열 방향으로 바로 붙어 있는 가게로만 걸어갈 수 있고, 도착한 가게에서 스탬프를 하나 더 받는다. 다만 같은 업종의 스탬프는 두 번 받을 수 없다. 즉 이미 받은 업종과 같은 알파벳이 적힌 가게에는 들어갈 수 없다.
참가자는 더 갈 곳이 없어지면 투어를 끝낸다. 출발한 가게에서 받은 스탬프도 개수에 넣어 센다. 상가의 업종 배치가 주어졌을 때, 한 참가자가 받을 수 있는 스탬프의 최대 개수를 계산하는 프로그램을 작성하여라.
예를 들어 R=3, C=6인 상가의 업종 배치가 다음의 표와 같다고 해보자.
| 칸 | 1열 | 2열 | 3열 | 4열 | 5열 | 6열 |
|---|---|---|---|---|---|---|
| 1행 | Z | I | Q | C | W | E |
| 2행 | Z | U | L | W | K | K |
| 3행 | Y | G | O | M | W | U |
이때 다음과 같이 걸어가면 스탬프를 11개 받을 수 있다.
| 순서 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 칸 | 1행 1열 | 1행 2열 | 2행 2열 | 3행 2열 | 3행 3열 | 2행 3열 | 1행 3열 | 1행 4열 | 1행 5열 | 1행 6열 | 2행 6열 |
| 업종 | Z | I | U | G | O | L | Q | C | W | E | K |
1행 1열의 Z에서 출발했으므로 2행 1열의 Z에는 들어갈 수 없고, 1행 5열의 W를 받았으므로 2행 4열과 3행 5열의 W에도 들어갈 수 없다. 12개 이상 받는 방법은 없으므로, 현재 예시의 정답은 11이다.
입출력 예시
예시 1
입력
3 6 ZIQCWE ZULWKK YGOMWU
출력
11
예시 2
입력
2 2 BB AA
출력
2
예시 3
입력
5 5 EDACD EEBEE DDAEE ABECB DCDCE
출력
4
입력 조건
가장 먼저 첫째 줄에 상가의 행의 수 R과 열의 수 C가 공백을 두고 주어진다. R과 C는 각각 1 이상 20 이하의 자연수다.
이어서 R개의 줄에 걸쳐 각 행의 업종 배치가 위쪽 행부터 차례대로 주어진다. 각 줄은 알파벳 대문자 C개가 공백 없이 이어진 문자열이며, 왼쪽 글자부터 1열, 2열, 차례대로 C열까지의 업종을 뜻한다. 같은 알파벳이 여러 칸에 나올 수 있다.
출력 조건
한 참가자가 받을 수 있는 스탬프의 최대 개수를 첫째 줄에 출력한다. 출발한 1행 1열의 가게에서 받은 스탬프도 개수에 넣어 세므로, 답은 항상 1 이상이다.
요구사항
- 출발하는 칸은 항상 1행 1열입니다
- 이동은 행 방향이나 열 방향으로 바로 붙어 있는 칸으로만 합니다
- 이미 받은 업종과 같은 알파벳이 적힌 칸에는 들어갈 수 없습니다
- 출발한 칸에서 받은 스탬프도 개수에 넣어 셉니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
2 2 BB AA
2
5 5 EDACD EEBEE DDAEE ABECB DCDCE
4
3 6 ZIQCWE ZULWKK YGOMWU
11
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.