아직 계정이 없으신가요? 회원가입

[인증평가(1차) 기출] 차세대 지능형 교통시스템
난이도
참가자 수
14
제출 수
35
정답률
21.74%
지원 언어
제한시간 : C/C++(1초), Java/Python(2초) | 메모리 제한 : 256MB


지능형 교통시스템(Intelligent Transport System)은 이미 우리의 삶에 밀접하게 연결되어 있다. 내비게이션 실시간 교통정보, 고속도로의 하이패스, 정류장의 버스 도착 안내 시스템들이 ITS에 속한다. 여기서 차량과 인프라가 서로 협력하면 차세대 지능형 교통시스템(C-ITS, Cooperative Intelligent Transportation System)이 되는 것이다. 이렇게 차량 주행과 관련된 인프라와 차량 등이 통신하기 시작하면 사고나 정체 상황에서 놀라운 일이 벌어진다.



여기 교통 인프라(신호등)와 실시간 통신을 하는 자율주행차가 가로, 세로 N개의 교차로로 구성된 도로를 지나고 있다. 교차로 간 연결된 선을 도로, 도로의 교차점들을 교차로로 생각하자. 자율주행 차는 처음에 제일 왼쪽 위의 교차로로 아래쪽 방향에서 진입하고 있다. (자동차는 도로 한 칸을 가는 데는 1T가 걸린다.)



각 교차로의 신호등은 다음과 같은 12가지 상태 중 4가지를 가지고 무한히 반복하는 방식으로 운영된다.



예를 들어 한 교차로의 신호 집합이 <3 2 6 10>과 같이 주어진 경우는 아래와 같다.



자율주행 자동차가 멈추지 않고, 시간 T 이내에 갈 수 있는 교차로의 수를 계산하라. 단, 신호가 맞지 않으면 그 교차로에는 갈 수가 없다. 처음에 제일 왼쪽 위의 교차로로 아래쪽 방향에서 진입하고 있으므로, 교차로(1,1)의 신호가 2, 10번 중 하나가 아니면 더 이상 진행을 할 수 없으므로 교차로는 단 하나[교차로(1,1)]로 계산한다.


부분문제
  (20점) N, T ≤ 5로 제한한다.
  (80점) 추가 제약 조건 없음.


입력형식
입력으로는 N과 시간 T가 첫 줄에 주어진다. (1 ≤ N, T ≤ 100)

다음 N2개의 줄에 각 교차로의 신호 집합이 주어진다. 신호는 항상 4개이며, 순서는 X축부터 진행을 한다.

예를 들어 N이 2인 경우
두 번째 줄. 교차로(1,1)의 신호
세 번째 줄. 교차로(2,1)의 신호
네 번째 줄. 교차로 (1,2)의 신호
마지막 줄. 교차로 (2,2)의 신호


출력형식
이동 경로에 있는 모든 교차로의 개수를 출력한다. 한번 갔던 교차로는 중복해서 세지 않는다.


입력예제
3 3
2 6 12 9
7 1 11 6
6 3 5 11
1 1 12 9
3 11 8 2
1 7 11 9
4 6 2 3
2 4 2 4
6 9 2 6


출력예제
6


예제 부연 설명
[T=0]
자율주행 자동차는 처음에 제일 왼쪽 위의 교차로로 아래쪽 방향에서 진입하고 있고, 그 때 교차로 A의 신호등은 2번이므로 우회전만 가능하다.
(이동 경로에 있는 교차로 1개 - 교차로 A)


[T=1]
교차로 B로 진입하고 있고, 그 때 교차로 B의 신호등은 1번이므로 직진과 우회전이 가능하다.
(이동 경로에 있는 교차로 2개 - 교차로 A, 교차로 B)


[T=2, case 1]
교차로 B를 통과해서 갈 수 있는 두가지 경로(교차로 C, 교차로 E 방향) 중, 교차로 C로 진입을 하게 될 때 교차로 C의 신호등은 5번으로 직진과 좌회전 신호이지만 더 이상의 진행은 불가능 하다.
(이동 경로에 있는 교차로 3개 - 교차로 A, 교차로 B, 교차로 C)


[T=2, case 2]
교차로 B를 통과해서 갈 수 있는 두가지 경로(교차로 C, 교차로 E 방향) 중, 교차로 E로 진입을 하게 될 때 교차로 E의 신호등은 8번으로 직진과 좌회전이 가능하다.
(이동 경로에 있는 교차로 3개 - 교차로 A, 교차로 B, 교차로 E)


[T=3, case 2-1]
교차로 E를 통과해서 갈 수 있는 두가지 경로(교차로 F, 교차로 H 방향) 중, 교차로 F로 진입을 하게 될 때 교차로 F의 신호등은 9번으로 직진과 우회전이나 우회전만 가능하다.
(이동 경로에 있는 교차로 4개 - 교차로 A, 교차로 B, 교차로 E, 교차로 F)


[T=3, case 2-2]
교차로 E를 통과해서 갈 수 있는 두가지 경로(교차로 F, 교차로 H 방향) 중, 교차로 H로 진입을 하게 될 때 교차로 H의 신호등은 4번으로 직진과 좌회전, 우회전이나 좌회전과 우회전만 가능하다.
(이동 경로에 있는 교차로 4개 - 교차로 A, 교차로 B, 교차로 E, 교차로 H)


그래서 T=0~3까지 시간동안 이동경로에 있는 모든 교차로는 총 6개 이다.
(교차로 A, 교차로 B, 교차로 C, 교차로 E, 교차로 F, 교차로 H)