题意：在一个长方形网格中有行（street）和列（avenue）。然后每两个点（x,y）之间有一条简单路径表示他们只要转一次弯。每各行和列都是单向的方向由你来决定。问你能不能满足所有给你的询问（a, b）都有一条a->b的简单路径。
思路：我们可以看到一共有m+n条路每条路都有两个方向可以选。这样就联想到了2-sat，然后就是分析题目
对于两个点当横坐标和纵坐标都不想等的时候我们会得到上面这种情况。(a^b)U(c^d) = (a U d)^(b U c)^(a U c)^(b U d)
对于横坐标纵坐标都想等我们不需要建边。然而有一个相等，若是a = 非a->a而非a = a->非a。
图建完后套模版就是了。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-01-29 19:07 5 * Filename : uva_10319.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN =10010; 34 const int ROW = 0; 35 const int COL = 1; 36 vector<int> Map[LEN], rMap[LEN], vs; 37 int n, m, vis[LEN], cmp[LEN]; 38 39 //pos | col or row | true or false 40 int ch(int pos, int f, int isf){ 41 return pos*2 + f*n*2 + isf; 42 } 43 44 void dfs(int v){ 45 vis[v] = 1; 46 for(int i=0; i<Map[v].size(); i++) 47 if(!vis[Map[v][i]]) dfs(Map[v][i]); 48 vs.PB(v); 49 } 50 51 void rdfs(int v, int f){ 52 vis[v] = 1; 53 cmp[v] = f; 54 for(int i=0; i<rMap[v].size(); i++) 55 if(!vis[rMap[v][i]]) rdfs(rMap[v][i], f); 56 } 57 58 int scc() 59 { 60 memset(vis, 0, sizeof vis); 61 vs.clear(); 62 for(int i=0; i<2*(n+m); i++)if(!vis[i])dfs(i); 63 memset(vis, 0, sizeof vis); 64 int f = 0; 65 for(int i=vs.size()-1; i>=0; i--)if(!vis[vs[i]])rdfs(vs[i], f++); 66 return f; 67 } 68 69 bool Judge(){ 70 scc(); 71 for(int i=0; i<2*(n+m); i+=2) 72 if(cmp[i] == cmp[i+1]) return false; 73 return true; 74 } 75 76 // a U b 77 void add(int a, int b){ 78 Map[a^1].PB(b); 79 Map[b^1].PB(a); 80 rMap[b].PB(a^1); 81 rMap[a].PB(b^1); 82 } 83 84 void addedge(int a, int b, int c, int d) 85 { 86 if(a == c && b == d) return ; 87 if(a != c && b != d){ // (a U d)^(b U c)^(a U c)^(b U d) 88 int _a = ch(a, ROW, d-b>0?0:1); 89 int _b = ch(b, COL, c-a>0?0:1); 90 int _c = ch(c, ROW, d-b>0?0:1); 91 int _d = ch(d, COL, c-a>0?0:1); 92 add(_a, _b); 93 add(_c, _d); 94 add(_a, _c); 95 add(_b, _d); 96 }else{ 97 if(a == c && d-b > 0){ 98 Map[ch(a, ROW, 1)].PB(ch(a, ROW, 0)); 99 rMap[ch(a, ROW, 0)].PB(ch(a, ROW, 1)); 100 } 101 if(a == c && d-b < 0){ 102 Map[ch(a, ROW, 0)].PB(ch(a, ROW, 1)); 103 rMap[ch(a, ROW, 1)].PB(ch(a, ROW, 0)); 104 } 105 if(b == d && c-a > 0){ 106 Map[ch(b, COL, 1)].PB(ch(b, COL, 0)); 107 rMap[ch(b, COL, 0)].PB(ch(b, COL, 1)); 108 } 109 if(b == d && c-a < 0){ 110 Map[ch(b, COL, 0)].PB(ch(b, COL, 1)); 111 rMap[ch(b, COL, 1)].PB(ch(b, COL, 0)); 112 } 113 } 114 } 115 116 int main() 117 { 118 // freopen("in.txt", "r", stdin); 119 120 int T, q, a, b, c, d; 121 scanf("%d", &T); 122 while(T--){ 123 for(int i=0; i<LEN; i++)Map[i].clear(); 124 for(int i=0; i<LEN; i++)rMap[i].clear(); 125 scanf("%d%d%d", &n, &m, &q); 126 for(int i=0; i<q; i++){ 127 scanf("%d%d%d%d", &a, &b, &c, &d); 128 addedge(a-1, b-1, c-1, d-1); 129 } 130 if(Judge()) printf("Yes "); 131 else printf("No "); 132 } 133 return 0; 134 }