首页 > 代码库 > hdu 1175
hdu 1175
http://acm.hdu.edu.cn/showproblem.php?pid=1175
一道bfs的水题吧,挺恶心的,YES,NO的大小写我没注意,然后WA
这个题吧好像有个BUG就是说这两个点有可能是在一起的,数据问题
1 #include <stdio.h> 2 #include <string.h> 3 #include <queue> 4 #define jud(Node) Node.x>0&&Node.x<m+1&&Node.y>0&&Node.y<n+1 5 using namespace std; 6 7 struct Node{ 8 int x,y; 9 int step; 10 }; 11 queue<Node>s; 12 int graph[1005][1005]; 13 int m,n,t; 14 int a,b,c,d; 15 int mark[1005][1005]; 16 int dic[4][2] = {0,1,1,0,0,-1,-1,0}; 17 18 void bfs() 19 { 20 memset(mark,true,sizeof(mark)); 21 Node tmp,tmp1; 22 tmp.x = a; 23 tmp.y = b; 24 tmp.step = -1; 25 mark[tmp.x][tmp.y] = false; 26 while(!s.empty()) 27 s.pop(); 28 s.push(tmp); 29 while(!s.empty()) 30 { 31 tmp = s.front(); 32 s.pop(); 33 if(tmp.x==c&&tmp.y==d&&tmp.step<=2) 34 { 35 printf("YES\n"); 36 return; 37 } 38 for(int i = 0; i<4; i++) 39 { 40 tmp1.x = tmp.x + dic[i][0]; 41 tmp1.y = tmp.y + dic[i][1]; 42 while(((graph[tmp1.x][tmp1.y]==0)||(tmp1.x==c&&tmp1.y==d))&&jud(tmp1)&&tmp.step<2) 43 { 44 if(mark[tmp1.x][tmp1.y]) 45 { 46 tmp1.step = tmp.step+1; 47 mark[tmp1.x][tmp1.y] = false; 48 s.push(tmp1); 49 // printf("%d %d %d %d\n",tmp.x,tmp.y,tmp1.x,tmp1.y); 50 } 51 Node tmp2; 52 tmp2.x = tmp1.x+dic[i][0]; 53 tmp2.y = tmp1.y+dic[i][1]; 54 tmp1 = tmp2; 55 } 56 } 57 } 58 printf("NO\n"); 59 } 60 61 int main() 62 { 63 64 while(scanf("%d%d",&m,&n),m||n) 65 { 66 memset(graph,0,sizeof(graph)); 67 for(int i = 1;i<=m;i++) 68 for(int j = 1;j<=n;j++) 69 scanf("%d",&graph[i][j]); 70 scanf("%d",&t); 71 while(t--) 72 { 73 scanf("%d%d%d%d",&a,&b,&c,&d); 74 if(graph[a][b]==0||graph[c][d]==0) 75 printf("NO\n"); 76 else if(graph[a][b]!=graph[c][d]) 77 printf("NO\n"); 78 else if(a==c&&b==d) 79 printf("NO\n"); 80 else bfs(); 81 } 82 } 83 return 0; 84 }
hdu 1175
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。