[일반] 2sat 틀리게 풀고 있는건가요?

[익명(175.195)]

https://www.acmicpc.net/problem/1739

행, 열이 증가하는 걸 참, 감소하는걸 거짓으로 해서 예를 들어 (x1, y1) 에서 오른쪽 아래에 있는 (x2, y2) 로 가려면 (x1 and y2) or (x2 and y1) 맞나요..?

만약 출발지와 도착지가 같은 선에 있으면 어떻게 표현해야 하나요?

[ㅁ(118.235)]

각 꼭짓점을 왼쪽 위부터 오른쪽 아래로 순서대로 A,B,C,D라고 할때, 만약 (B->A)라는 경로가 이미 세워져 있으면 (A->C),(C->D)라는 경로는 반드시 존재해야 하겠지. 그래서 만약 경로 1개가 역방향이다 하면 다른 적당한 2개 경로가 반드시 정방향이여야 한다고 설정해두면 이건 투셋이됨

[ㅁ(118.235)]

아 A에거 D까지가는걸로 가정할때. 아무튼 이렇게 하면 한 버스경로당 8개의 SAT이 만들어지겠지. 그렇게 일단 투샛식을 만들고 이제 A와 D가 한줄에 있는 경우인데, 얘내는 무조건 참인 경우로 따로 저장해둠. 나중에 투샛 만들어진 경우에서 따로 저장한 애들이 전부 참이라 가정할때, 모순만 안일어나면 됨. 모순이란건 A->D와 D->A가 전부 참인 경우를 의미하고

[익명(211.107)]

오.. 형님 고맙습니다 다시 트라이해보겠습니다