Problems
N*M 크기의 격자가 주어진다. 일부 칸은 막혀서 움직일 수 없는 칸이고, 나머지 칸들은 서로 자유자래로 움직일 수 있는 칸이다. 여기에 페인트를 칠하려고 한다.
페인트를 칠하는 규칙은 다음과 같다.
1) 움직일 수 있는 칸 아무거나 하나를 시작점으로 잡을 수 있다.
2) 이제 가로방향 또는 세로방향으로 움직일 수 있는데, 가로방향으로 움직일 때는 파란색 페인트로, 세로방향으로 움직일 때는 노란색 페인트를 이용한다.
3) 바닥이 굉장히 미끄럽기 때문에 중간에 멈출수가 없다. 즉, 한쪽 방향으로 계속 움직여 격자에 끝에 도달하거나 움직일 수 없는 칸에 도착했을 때만 움직임을 멈추고 방향을 바꿀 수 있다.
위 과정을 무한히 반복했을 때, 움직일 수 있는 모든 칸에 노란색 페인트와 파란색 페인트가 모두 적어도 한번씩 칠해질 수 있는지 판별하시오.
Input
첫 줄에 N과 M이 주어진다. (1<=N, M<=1000)
그 다음 N행 M열의 격자가 주어진다. '.'은 움직일 수 있는 칸, '#'은 움직일 수 없는 칸을 의미한다.
Subtask #1(30점) : N, M<=50
Subtask #2(70점) : 추가 제한 없음
Output
위 과정을 무한히 반복했을 때, 움직일 수 있는 모든 칸에 노란색 페인트와 파란색 페인트가 모두 적어도 한번씩 칠해질 수 있다면 1, 아니면 0을 출력하시오.
Example #1
1 1
.
1
Example #2
2 3
...
...
1
Example #3
3 3
...
..#
.##
1
Example #4
3 3
.##
#..
#..
Tag
Source
2020 1차 선발고사
You must sign in to write code.