首页 > 代码库 > 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 }
lianliankan
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。