부산과 거제도를 잇는 거가대교가 개통된 이래로 거제도에는 많은 피서객들이 방문한다. 거제도 펜션 예약 담당자의 업무는 고객이 요구하는 일정에 맞추어 방을 예약해 주는 것이다. 여름 성수기 동안은 고객이 요청한 일정 내내 같은 방을 예약해 줄 수 없는 경우가 많다. 그런 경우 여러 방을 옮겨 지낼 수 있는 방법을 찾아서 고객에게 제시해 주는데, 가능한 방을 옮기는 횟수가 최소가 되도록 해 주어야 한다. 고객은 항상 정오 이후에 펜션에 도착하여 정오 이전에 떠나야 한다.

현재 펜션의 예약 상태와 고객의 일정이 주어질 때, 펜션 직원의 업무를 도와줄 수 있는 프로그램을 작성하시오.

1. 첫째 줄에 두 개의 정수 n과 m이 주어진다. n은 펜션에서 관리하는 여름 성수기 총 기간을 나타내고, m은 펜션이 보유하고 있는 방의 개수이다(1≤n≤100, 3≤m≤30). 편의상 성수기 기간을 1일부터 n일까지로 표시하고, 펜션의 방을 1부터 m까지의 번호로 구분한다.
2. 그 다음 n개의 줄에는 각 줄마다 길이가 m인 문자열이 주어진다. 입력에서 i+1 번째 줄의 j-번째 문자는 여름 성수기 기간 중 i-번째 날에 방 번호가 j인 방의 예약 상태를 나타낸다(1≤i≤n, 1≤j≤m). 이 문자는 방이 이미 예약된 경우에는 "X", 그렇지 않으면 "O"이다. k-번째 날을 예약하면 그 다음 날 정오까지 방을 사용할 수 있다는 것을 의미한다.
3. 마지막 줄에는 고객의 일정을 나타내는 두 개의 정수 s, t가 주어진다, s는 펜션에 도착하는 날이고 t는 펜션을 떠나는 날이다(1≤s

1. 첫째 줄에 예약 기간 동안 방을 옮기는 최소 횟수를 출력한다.
2. 만일, 방을 옮기지 않아도 되는 경우는 0, 예약이 불가능한 경우는 -1을 출력한다.

설명 : 고객은 2일에 도착하여 9일에 떠난다. 2일 정오에서 5일 정오까지는 2번 방을 배정하고, 5일 정오부터 9일 정오까지는 6번 방을 배정해 준다. 따라서 고객은 방을 한 번 옮기면 된다.

교원프로그래밍 2011