首页 > 代码库 > lianliankan

lianliankan

  1 #include<iostream>  2 #include<cstdio>  3 #include<cmath>  4 #include<cstdlib>  5 #include<cstring>  6 #include<queue>  7 using namespace std;  8 int map[1005][105];  9 int vis[1005][105]; 10 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; 11 int n,m; 12 int x1i,y1j,x2i,y2j; 13 int flag; 14 struct ln{ 15     int x; 16     int y; 17     int step; 18 }abc,q; 19  20 int border(int x,int y) 21 { 22     if(x>=1&&x<=n && y>=1&&y<=m) 23     { 24         if(!map[x][y] && !vis[x][y] ) 25         return 1; 26     } 27     return 0; 28 } 29  30 void bfs() 31 { 32     int i; 33     queue<struct ln>p; 34     memset(vis,0,sizeof(vis)); 35     abc.x=x1i; 36     abc.y=y1j; 37     abc.step=-1; 38     vis[abc.x][abc.y]=1; 39     p.push(abc); 40     while(!p.empty()) 41     { 42         abc=p.front(); 43         p.pop(); 44         if( abc.x==x2i && abc.y==y2j && map[abc.x][abc.y]==map[x2i][y2j] && abc.step<=2 ) 45         { 46             flag=1; 47             return ; 48         } 49         q.step=abc.step+1; 50  51  52         for(i=0;i<4;i++) 53         { 54             q.x=abc.x+dir[i][0]; 55             q.y=abc.y+dir[i][1]; 56             while(border(q.x,q.y)) 57             { 58                 if(!vis[q.x][q.y]) 59                 { 60                     vis[q.x][q.y]=1; 61                     p.push(q); 62                 } 63                 q.x+=dir[i][0]; 64                 q.y+=dir[i][1]; 65             } 66         } 67     } 68     return ; 69 } 70  71 int main() 72 { 73     while(~scanf("%d%d",&n,&m)) 74     { 75         if(!n&&!m) 76         break; 77         int i,j; 78         for(i=1;i<=n;i++) 79         { 80             for(j=1;j<=m;j++) 81             { 82                 scanf("%d",&map[i][j]); 83             } 84         } 85         int q; 86         scanf("%d",&q); 87         for(i=1;i<=q;i++) 88         { 89             flag=0; 90             scanf("%d%d%d%d",&x1i,&y1j,&x2i,&y2j); 91             if(map[x1i][y1j]!=map[x2i][y2j]) 92             { 93                 printf("NO\n"); 94                 continue; 95             } 96             else if(map[x1i][y1j]==0&&map[x2i][y2j]==0) 97             { 98                 printf("NO\n"); 99                 continue;100             }101 102             bfs();103             if(flag==1)104             printf("YES\n");105             else106             printf("NO\n");107 108         }109 110 111     }112     return 0;113 }
View Code

 

lianliankan