31669번 - 특별한 학교 탈출 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 955 | 677 | 637 | 71.573% |
문제
NLCS Jeju의 학생들은 수업에 질려 학교에서 탈출하고 싶어한다. 수업 시간에 학교에서 탈출하는 것은 어려운 일이다.
NLCS Jeju의 수업 시간은 $1$교시부터 $M$교시이다. 또한 NLCS Jeju에 있는 $N$명의 선생님들은 각각 $1$교시부터 $M$교시 사이에 정해진 스케줄에 따라 해당 수업 시간 동안 순찰한다. 학교에서 탈출하다 선생님에게 들키면 안 되기 때문에 학생들은 아무도 순찰하지 않을 때 학교에서 탈출해야 한다. 학교 탈출을 시도하려는 시각에 순찰하는 선생님이 있다면 선생님에게 무조건 들킨다.
각 선생님의 순찰 스케줄이 주어질 때 학생들이 학교에서 탈출할 수 있는지 판단하고, 가능하다면 학교에서 탈출할 수 있는 가장 빠른 시각을 구하자.
입력
첫 번째 줄에 선생님의 수 $N$과 수업 시간의 수 $M$이 공백으로 구분되어 주어진다.
두 번째 줄부터 $N+1$번째 줄까지 O와 X로 이루어진 길이 $M$의 문자열이 주어진다. $j+1$번째 줄의 $i$번째 문자가 O이면 $i$번째 시각에 $j$번째 선생님이 순찰하고, X이면 $i$번째 시각에 $j$번째 선생님이 순찰을 하지 않는다.
출력
학생들이 선생님에게 들키지 않고 가장 빠르게 학교에서 탈출했을 때가 몇 교시인지 출력하라. 학생들이 선생님에게 들키지 않고 학교에서 탈출할 수 없다면 ESCAPE FAILED를 출력하라.
제한
- $1 \le N,M \le 100$
예제 입력 1
5 5 OXXOO XXXOX OOXXX OXXOO XOXXO
예제 출력 1
3
예제 입력 2
5 5 OXXXX XOXXX XXOXX XXXOX XXXXO
예제 출력 2
ESCAPE FAILED
예제 입력 3
7 5 OOXXO OXXOO XOXXX XOOOX OOOXX OXOOO XOOXO
예제 출력 3
ESCAPE FAILED