hdu1175-连连看（dfs）

一个一个走，记录方向改变了几次，不能超过两次，两次如果还没到终点return；
 1 #include<cstdio>
 2 
 3 #include<string.h>
 4 
 5 #define inf 0x3f3f3f3f
 6 
 7 const int maxn=1000;
 8 
 9 using namespace std;
10 
11 const int dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
12 
13 int flag[maxn+10][maxn+10];
14 
15 int n,m,q;
16 
17 int sx,sy,gx,gy;
18 
19 int a[maxn+10][maxn+10];
20 
21 int dfs(int x,int y,int dirc,int turn){
22   //printf("%d %d %d %d
",x,y,dirc,turn);
23    if(turn>2) return 0;
24    if(x==gx&&y==gy){
25         return 1;
26    }
27    for(int i=0;i<4;i++){
28         if(turn==2&&i!=dirc) continue;
29         int nx=x+dir[i][0];
30         int ny=y+dir[i][1];
31         if(nx==gx&&ny==gy){
32                 if(i==dirc||dirc==-1) return 1;
33                 else if(i!=dirc&&turn+1<=2) return 1;
34                 continue;
35         }
36         if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!flag[nx][ny]&&!a[nx][ny]){
37                 if(i==dirc||dirc==-1){
38                         flag[nx][ny]=1;
39                         if(dfs(nx,ny,i,turn)) return 1;
40                 } else if(i!=dirc){
41                    flag[nx][ny]=1;
42                    if(dfs(nx,ny,i,turn+1)) return 1;
43                 }
44                 flag[nx][ny]=0;
45         }
46    }
47    return 0;
48 }
49 
50 int main()
51 {
52     while(scanf("%d%d",&n,&m)!=EOF){
53         if(n==0&&m==0)  break;
54         for(int i=1;i<=n;i++){
55                 for(int j=1;j<=m;j++){
56                         scanf("%d",&a[i][j]);
57                 }
58         }
59         scanf("%d",&q);
60         while(q--){
61            memset(flag,0,sizeof(flag));
62            scanf("%d%d%d%d",&sx,&sy,&gx,&gy);
63            if(!a[sx][sy]||!a[gx][gy]||a[sx][sy]!=a[gx][gy]){
64                 printf("NO
");
65                 continue;
66            }
67            if(dfs(sx,sy,-1,0)) printf("YES
");
68            else printf("NO
");
69         }
70     }
71     return 0;
72 }