【ACM】连连看 hdu1175

此题需要注意：
1.不能从外围绕过。
2.有可能询问的两个点都是空点。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <math.h>
 4 using namespace std;
 5 
 6 const int MAXN=1000+5;
 7 const int INF=100000000;
 8 
 9 int map[MAXN][MAXN];
10 int m,n,q,a,b,c,d;
11 
12 int max(int a,int b){
13     if(a>b)return a;
14     return b;
15 }
16 int min(int a,int b){
17     if(a<b)return a;
18     return b;
19 }
20 
21 bool lineok(int x1,int y1,int x2,int y2){
22 
23     if(x1==x2 && y1==y2)return true;
24 
25     int minx = min(x1, x2);
26     int miny = min(y1, y2);
27     int maxx = max(x1, x2);
28     int maxy = max(y1, y2);
29     
30     if (x1 == x2){
31         for (int i = miny; i <= maxy; i++) if ( map[x1][i]!=0 ) return false;
32     }
33     else {
34         for (int i = minx ; i <= maxx; i++) if ( map[i][y1]!=0 ) return false;
35     }
36     return true;
37 }
38 bool ok(int x1,int y1,int x2,int y2){
39 
40     if(map[x1][y1]==0 || map[x2][y2]==0)return false;
41 
42     if (x1 == x2 && y1 == y2) return false;
43 
44     if ( map[x1][y1] != map[x2][y2] ) return false;
45 
46     bool pri_ok = false;
47     int t1=map[x1][y1],t2=map[x2][y2];
48     map[x1][y1]=0;
49     map[x2][y2]=0;
50 
51     for (int i = 1; i <= m; i++){
52         //如果你想从外围绕过，就改为for(int i=0; i<=m+1 ;i++)
53         if (lineok(x1, y1, i, y1) && lineok(i, y1, i, y2) && lineok(i, y2, x2, y2)){
54             pri_ok = true;
55             break;
56         }
57                     
58     }
59     if (pri_ok == false){
60         for (int i = 1; i <= n; i++){
61             //如果你想从外围绕过，就改为for(int i=0; i<=n+1 ;i++)
62             if (lineok(x1, y1, x1, i) && lineok(x1, i, x2, i) && lineok(x2, i, x2, y2)){
63                 pri_ok = true;
64                 break;
65             }
66 
67         }
68     }
69     map[x1][y1]=t1;
70     map[x2][y2]=t2;
71 
72     if (pri_ok) return true;
73     else return false;
74 }
75 
76 int main(){
77     while(scanf("%d %d",&m,&n) && m &&n){
78         memset(map,0,sizeof map);
79         for(int i=1;i<=m;i++){
80             for(int j=1;j<=n;j++){
81                 scanf("%d",&map[i][j]);
82             }
83         }
84         scanf("%d",&q);
85         while(q--){
86             scanf("%d %d %d %d",&a,&b,&c,&d);
87             if( ok(a,b,c,d) )printf("YES
");
88             else printf("NO
");
89         }
90     }
91     return 0;
92 }