시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB285402823.729%

문제

2005년 1월 14일 밤 파라다이스 감옥에서 죄수들이 탈출을 감행하려 한다. 어찌어찌하다 이 사실을 알게 된 간수장. 간수장은 길목마다 간수들을 배치해 탈출을 막아보기로 했다. 하지만 이를 위해서는 간수들에게 추가 수당을 지급해야만 하는데... 왠지 돈이 아깝다. 때문에 적은 수의 간수를 감옥내에 배치하려고 하는데... (단, 간수들은 깜깜한 어둠속에서는 자기 옆으로 죄수가 지나가도 알아챌수 없다. 그리고 죄수들은 대각선으론 움직일 수 없다.)

입력

첫 번째 줄에는 정방형 감옥의 크기 N과 일할수 있는 간수들의 수가 주어진다. 두 번째 줄부터는 감옥의 구조가 주어진다. '+'는 벽, 'X'는 감옥을 탈출하려는 죄수들의 위치이다. 'O'는 바깥으로 나갈수 있는 문들의 위치이다. 감옥의 문은 하나 이상이다.

출력

K명의 간수들로 모든 죄수들의 탈출을 막을수 있다면 첫줄에 Yes 그렇지 않다면 No를 출력한다. 만약 막을수 있다면 두 번째 줄에 필요한 간수들의 최소 수를 출력하여라.

제한

  • 1 ≤ N ≤ 100
  • 0 ≤ K ≤ 1,000

예제 입력 1

5 4
X....
.+++.
.+.+.
.....
.X+.O

예제 출력 1

Yes
2