피파 온라인 드리블 튜토리얼

피파 온라인 게임에서는 드리블 훈련을 하기 위한 간단한 세로 스크롤 게임을 제공한다. 이 게임에서 사용자는 축구공을 드리블하는 주인공 선수를 조종한다. 게임 판은 $N$행 $M$열의 격자칸으로 생각할 수 있다. 화면에 한번에 보이는 부분은 게임 판의 일부인 $K$행 $M$열이다.

게임 판의 각 격자칸은 빈칸이거나 혹은 상대 선수가 있다. 주인공 선수는 게임 판의 격자칸들로 움직일 수 있다.

게임이 시작할 때 게임 판의 제일 아래 $K$행 $M$열이 화면에 보인다. 주인공 선수는 게임 판의 가장 왼쪽 아래 격자에 있다.

이후 다음과 같은 두가지가 계속 반복된다.

1. 주인공 선수를 상하좌우로 인접한 격자칸으로 이동할 수 있다. 주인공 선수가 가만히 있을 수도 있다. 주인공 선수는 화면의 범위 밖으로 나갈 수 없다.
2. 게임 판이 아래로 한 칸 스크롤된다. (주인공 선수는 화면 상에서 같은 위치가 유지된다. 즉, 게임 판 기준으로는 주인공 선수가 위로 한칸 움직인다.)

위 과정을 반복할 때 주인공 선수와 상대 선수가 겹치게 되면 게임에 실패한다. 화면이 끝까지 스크롤되면 게임에 성공한다. 즉, 게임 판의 제일 위 $K$행 $M$열이 화면에 나타나는 것이 성공이다.

주인공 선수는 1)번 단계 직후 축구공을 정면으로 강하게 차서 상대 선수 한 명을 게임 판에서 없어지도록 할 수 있다. 이때 없어지는 상대 선수는 주인공 선수의 정면에서 (화면 상에서 위쪽으로) 가장 가까운 선수이다. 또, 이 상대 선수는 화면에 보이는 상태라야 한다.

게임 판의 상황을 입력으로 받아 주인공 선수가 게임에 성공하기 위해 축구공을 강하게 차야 하는 최소 횟수를 출력하는 프로그램을 작성하라.

입력 형식

첫째 줄에 게임 판과 화면의 크기를 알려주는 $N$, $M$, $K$가 주어진다.

다음 $N$개의 줄 각각에 게임 판의 한 행이 $M$개의 글자로 주어진다. 글자가 .(점)인 경우 빈 칸이며, 글자가 #인 경우 상대 선수가 있는 것이다. ($2 \le K \le 50$, $1 \le M \le 50$, $2 \times K < N \le 500$)

입력의 첫 $K$줄과 마지막 $K$줄은 모두 .(점) 문자이다.

출력 형식

주인공 선수가 게임에 성공하기 위해 축구공을 강하게 차야 하는 최소 횟수를 정수로 출력한다.

예제 1

5 4 2
....
....
##.#
....
....

0

예제 2

6 4 2
....
....
....
###.
....
....

1

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설