수로
시간 제한3초메모리 제한256 MB
격자에서 왼쪽 위 칸부터 오른쪽 아래 칸까지 가는 가장 긴 경로를 찾습니다. 경로는 대각선으로도 자기 자신과 닿으면 안 됩니다.
문제
전직 챔피언 코더 조는 드디어 농장을 샀다. 아, 죽은 것이 아니다. 멀쩡히 살아 있다. 그는 프로그래밍 대회 상금으로 조상 대대로 물려받은 농장을 사들였다. 은퇴해서 남은 날들을 소를 돌보며 보내고 싶어 하고, 어쩐 이유인지 스스로 소 전문가라고 여긴다.
하지만 조의 소박한 바람은 이루어지지 않는다. 농장은 춥고 북쪽에 있어서 소가 살기에는 너무 춥다. 게다가 땅이 건조해서 작물을 키우기도 어렵다. 조는 밭에 관개 시설을 만들어야 한다는 것을 깨닫는다. 이 계획은 강의 일부를 돌려 밭을 가로지르는 길고 구불구불한 수로로 흘려보내는 것이다. 수로에 가장 가까운 작물이 잘 자라므로 수로가 길수록 좋다.
밭은 단위 정사각형으로 나뉜 길고 직사각형 모양의 땅이다. 각 칸은 흙이면 '.', 움직일 수 없는 바위이면 '#'으로 표시한다. 수로의 폭은 한 칸이며, 밭의 왼쪽 위 모서리에서 들어와 오른쪽 아래 모서리로 나간다. 수로는 바위를 지나갈 수 없다. 수로는 모서리에서 닿는 경우까지 포함해서 자기 자신과 닿으면 안 된다. 닿으면 물이 스며들어 지름길로 빠지기 때문이다. 그림 3과 그림 4에 수로가 자신과 닿는 예가 나와 있다.
조의 프로그래밍 전성기는 이미 오래전 일이다. 그에게는 단순한 풀이법이 있지만 너무 오래 걸린다. 최적의 수로 배치를 찾는 것을 도와주겠는가?
입력
입력은 여러 개의 테스트 케이스로 이루어지며, 최대 20개이다. 각 테스트 케이스의 첫 줄에는 밭의 행 수 ()과 열 수 ()가 주어진다. 이어서 개의 줄에 길이 인 문자열이 주어지며 밭의 상태를 나타낸다. 마지막 테스트 케이스 다음에는 0 0이 주어진다.
출력
각 테스트 케이스마다 Case 1: 형식으로 케이스 번호를 출력한다. 이어서 가장 긴 수로를 배치한 결과를 개의 줄에 출력한다. 수로는 'C'로 표시한다. 답은 항상 하나로 정해진다. 예시 출력의 형식을 따른다. 각 테스트 케이스의 출력 뒤에는 빈 줄을 하나 출력한다.