점프하는 개구리
면접 대비시간 제한1초메모리 제한1024 MB
막힌 칸이 섞인 길에서 한 번에 최대 d칸을 넘어 뛸 때, 첫 칸에서 마지막 칸까지 가는 최소 점프 횟수를 구합니다.
문제
개구리 프레디는 먹을 것을 사러 가려고 하지만, 그가 좋아하는 식당은 모두 멀리 떨어져 있다. 프레디는 많은 칸을 뛰어넘을 수 있는 유능한 개구리다. 다만 날에 따라 배가 너무 고파서 멀리 뛰지 못하기도 한다. 어떤 날에는 한 번의 점프로 최대 개의 칸을 뛰어넘을 수 있다(더 적은 칸을 뛰어넘는 것도 가능하다).
프레디가 지나는 길은 항상 공사 중이어서 일부 칸이 막혀 있다. 프레디는 막힌 칸에 착지할 수 없지만, 그 위를 뛰어넘을 수는 있다.
프레디는 첫 번째 칸에서 출발해 식당이 있는 마지막 칸까지 가야 한다. 그는 항상 목적지 방향으로 뛴다. 식당에 도달하는 데 필요한 최소 점프 횟수를 구하라.
입력
첫째 줄에 확인할 날의 수 n이 양의 정수로 주어진다. 각 날은 두 줄로 나타낸다. 각 날의 첫 줄에는 두 정수 c와 d가 주어진다. 단, , 이다. c는 프레디의 집에서 식당까지 이어지는 길의 칸 수(양 끝 포함)이고, d는 그날 한 번의 점프로 뛰어넘을 수 있는 최대 칸 수다. 둘째 줄은 길이 c의 문자열이며, 각 문자는 '.' 또는 'X'다. '.'은 올라서도 되는 칸, 'X'는 공사로 막힌 칸을 뜻한다. 첫 번째 문자와 마지막 문자는 막혀 있지 않다.
출력
각 날마다 'Day #k' 형식의 머리말을 출력한다. k는 1부터 시작한다. 이어서 입력에 주어진 값을 입력에 나온 그대로 출력한다(c와 d가 있는 줄, 문자열 줄). 그다음 식당에 도달하는 데 필요한 최소 점프 횟수를 출력한다. 도달할 수 없으면 0을 출력한다. 각 날의 출력 뒤에는 빈 줄을 하나 남긴다.