당신에게 임무가 주어졌다. 도시의 도로를 디자인 하는 것이다. 당신의 도시에는 수평으로 나있는 도로가 있고 수직으로 나있는 도로가 있어 격자를 이루고 있다. 디자인 한다는 것은 각각의 수평, 수직도로의 방향을 결정하는 것이다. 각 도로는 결정된 단 하나의 방향으로만 이동해야 한다. 또한 시민들은 당신에게 자신들의 요구사항을 말해줄 것이다. '요구'는 자신이 원하는 시작 위치에서 끝 위치까지 단순한 경로가 하나 이상 존재해야 한다는 것이다. 아래의 그림을 보도록 하자. 시민 한사람의 요구사항이 그림과 같을 때 a)는 불가능한 경로이다. 왜냐하면 도로의 방향대로 움직이지 않았기 때문이다. b)는 가능한 경로이긴 하지만 단순한 경로가 아니다. 단순한 경로는 정확히 한 번 굴절된 경로를 말한다. c)만이 시민이 요구하는 단순한 경로이다.
당신이 해야 할 일은 시민들의 요구사항을 모두 만족하도록 도로를 디자인 할 수 있는지 없는지를 결정하는 프로그램을 작성하는 것이다.
입력 형식
첫 번째 줄에는 입력데이터의 개수가 주어진다. 두 번째 줄에는 도로의 개수들 V, H가 입력된다. V는 수직도로의 개수이고 H는 수평도로의 개수이다. V와 H는 30보다 작거나 같다. 같은 줄에 시민들의 요구사항의 개수 N이 주어진다. N은 200보다 작은 수이다. 다음 N개의 줄에는 시민들의 요구사항이 입력되는데 하나의 요구사항은 두 개의 좌표 x1, y1, x2, y2로 이루어져 있다. 두 좌표 중 처음 좌표는 시작위치이고 두 번째 좌표는 도착위치이다. 하나의 좌표 x, y라는 것은 x번째 수직도로와 y번째 수평도로가 만나는 지점을 의미한다. 각 숫자의 범위는 0 < x1, x2 <= V, 0 < y1, y2 <= H 이다.
출력 형식
시민들의 요구사항을 모두 만족하면서 도로를 디자인 할 수 있으면 'Yes'를 그럴수 없으면 'No'를 출력한다.
각 도로(수평도로 + 수직도로)의 상태(왼쪽 또는 오른쪽, 위 또는 아래)를 각각 하나의 정점으로 만든다.
이 문제의 경우, V개의 도로가 각각 두개(위, 아래), H개의 도로가 각각 두개(왼쪽, 오른쪽)의 정점을 지녀, 총 2*(V+H)개의 정점을 만들면 된다.
그리고 문제의 조건(시민들의 요구사항)을 하나씩 검토한다.
각 조건은 두 개의 좌표(x1, y1), (x2, y2)를 가지는데, 이 조건을 만족시킬 수 있는 방법은 다음의 두 가지 이다.
x1번째 수직도로로 y1->y2까지 간 다음, y2번째 수평도로로 x1->x2까지 가는 방법과, y1번째 수평도로로 x1->x2까지 간 다음, x2번째 수직도로로 y1->y2까지 가는 방법이다.
만약 y1 < y2라면, 수직도로의 방향은 위쪽이 되겠고, y1 > y2라면 수직도로의 방향은 아래쪽이 될 것이다. 수평도로도 같은 방법으로 결정한다. x1번째 수직도로와 그 방향을 나타내는 정점을 X1이라 하고, 나머지 정점들도 그와 같이 표기하도록 하자. (예를 들어 y2번째 수평도로와 그 방향은 Y2라 표기할 수 있겠다)
위의 조건에 의해 (X1 and Y2) or (Y1 and X2)가 되고,
집합의 분배법칙(?)에 의해 (X1 or Y1) and (X1 or X2) and (Y2 or Y1) and (Y2 or X2)와 같게 된다. 또한 각각의 (A or B)는 (^A -> B) and (^B -> A)와 같이 쓸 수 있기 때문에, 결과적으로 하나의 조건은 8개의 명제로 나타낼 수 있게 된다.
이해를 돕기위해 조금만 써보면, (^X1 -> Y1) and (^Y1 -> X1) and (^X1 -> X2) and (^X2 -> X1) and (^Y2 -> Y1) and ...
자 이제 위의 명제를 가지고 그래프로 나타내 보자. 위에서 우린 각각의 정점과 그 방향을 하나의 정점으로 나타내기로 하였다. ㅇㅋ 위에서 X1, X2, ^Y1, Y2 등등등... 써놓은게 결국 다 정점이란거다. 그럼 (^X1 -> Y1) 이런건 간선이 된다는거다.
하나의 조건당 8개의 간선을 만든 우린 이제 모든 조건을 만족하는 선택이 존재하는지만 찾으면 된다. 이게 의외로 간단한게 그래프를 Strongly Connected Component로 묶어준 다음에, 같은 Component 안에 어떤 A와 ^A가 함께 들어있는지만 검사해 주면 된다. 아 쉽다 :)
