两题基本相同
都是关于转弯不能超过某个数，所以有些点可能重复走，所以要设time[][]数组来记录上次走过的时间！！！！
记得初始化queue！！！
HDU1175
View Code
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7 const int dx[]={0,0,1,-1}; 8 const int dy[]={1,-1,0,0}; 9 const int maxn = 1005; 10 const int inf = 12345; 11 int mat[ maxn ][ maxn ],time[ maxn ][ maxn ]; 12 struct node{ 13 int x,y; 14 }s,e; 15 struct node2{ 16 int x,y,t,dir; 17 }p,pp; 18 queue<node2>q; 19 void init(){ 20 memset( mat,0,sizeof( mat ) ); 21 } 22 int n,m; 23 int out( int x,int y ){ 24 if( x<0||x>=n||y<0||y>=m ) 25 return 1; 26 else 27 return -1; 28 } 29 bool bfs(){ 30 for( int i=0;i<n;i++ ) 31 for( int j=0;j<m;j++ ) 32 time[i][j]=inf; 33 p.x=s.x,p.y=s.y,p.t=0,p.dir=-1; 34 time[ s.x ][ s.y ]=0; 35 q.push( p ); 36 while( !q.empty() ){ 37 p=q.front(),q.pop(); 38 //printf("front:%d %d t:%d\n",p.x,p.y,p.t); 39 if( p.t>2 ) 40 continue;//return false; 41 if( p.x==e.x&&p.y==e.y ) 42 return true; 43 for( int i=0;i<4;i++ ){ 44 pp.x=p.x+dx[i]; 45 pp.y=p.y+dy[i]; 46 pp.dir=i; 47 pp.t=p.t; 48 if( p.dir==-1 ){ 49 pp.t=p.t; 50 } 51 else if( pp.dir!=p.dir ){ 52 pp.t=p.t+1; 53 } 54 if( out( pp.x,pp.y )==1 ) 55 continue; 56 if( time[ pp.x ][ pp.y ]>pp.t&&( (pp.x==e.x&&pp.y==e.y)||mat[pp.x][pp.y]==0 ) ){ 57 time[ pp.x ][ pp.y ]=pp.t; 58 //printf("%d %d t:%d\n",pp.x,pp.y,pp.t); 59 q.push( pp ); 60 } 61 } 62 } 63 return false; 64 } 65 int main(){ 66 while( scanf("%d%d",&n,&m)==2,n+m ){ 67 init(); 68 for( int i=0;i<n;i++ ) 69 for( int j=0;j<m;j++ ) 70 scanf("%d",&mat[i][j]); 71 int num; 72 scanf("%d",&num); 73 while( num-- ){ 74 while( !q.empty() ) 75 q.pop(); 76 scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y); 77 s.x--,s.y--,e.x--,e.y--; 78 if( s.x==e.x&&s.y==e.y ){ 79 printf("NO\n"); 80 continue; 81 } 82 if( mat[s.x][s.y]==0||mat[e.x][e.y]==0||mat[s.x][s.y]!=mat[e.x][e.y] ){ 83 printf("NO\n"); 84 continue; 85 } 86 if( bfs()==true ){ 87 printf("YES\n"); 88 } 89 else{ 90 printf("NO\n"); 91 } 92 } 93 } 94 return 0; 95 }
HDU1728
View Code
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<queue> 5 #include<iostream> 6 using namespace std; 7 struct point{ 8 int x,y,dir,step; 9 }; 10 const int N=105; 11 const int MAX=999999; 12 const int dx[]={1,-1,0,0}; 13 const int dy[]={0,0,1,-1}; 14 char map[N][N]; 15 int time[N][N]; 16 int sx1,sy1,sx2,sy2,m,n,ans,tmp; 17 queue<point>q; 18 19 void bfs(){ 20 int i,j,k; 21 point p,pp; 22 if(sx1==sx2&&sy1==sy2){ 23 ans=0; 24 return ; 25 }//特殊情况1 26 while(!q.empty()) 27 q.pop(); 28 29 p.x=sx1; 30 p.y=sy1; 31 p.dir=-1; 32 p.step=0; 33 q.push(p); 34 time[p.x][p.y]=0;//init 35 36 while(!q.empty()){ 37 p=q.front(); 38 q.pop(); 39 if(p.x==sx2&&p.y==sy2&&ans>p.step){ 40 ans=p.step; 41 } 42 for(i=0;i<4;i++){ 43 pp=p; 44 pp.x+=dx[i]; 45 pp.y+=dy[i]; 46 if(pp.x<0||pp.x>=m||pp.y<0||pp.y>=n||map[pp.x][pp.y]=='*') 47 continue; 48 if(pp.dir!=-1&&pp.dir!=i){ 49 pp.step=p.step+1; 50 }//方向变了 51 if(pp.step>tmp)continue; 52 if(time[pp.x][pp.y]>=pp.step){ 53 pp.dir=i; 54 time[pp.x][pp.y]=pp.step; 55 q.push(pp); 56 } 57 } 58 } 59 //printf("no\n"); 60 return ; 61 } 62 63 int main(){ 64 int i,j,k,t; 65 scanf("%d",&t); 66 while(t--){ 67 scanf("%d%d",&m,&n); 68 getchar(); 69 for(i=0;i<m;i++){ 70 scanf("%s",map[i]); 71 getchar(); 72 } 73 /*for(i=1;i<=m;i++) 74 for(j=1;j<=n;j++){ 75 cin>>map[i][j]; 76 time[i][j]=MAX; 77 }*/ 78 scanf("%d%d%d%d%d",&tmp,&sy1,&sx1,&sy2,&sx2); 79 sy1--;sx1--;sy2--;sx2--; 80 for(i=0;i<m;i++) 81 for(j=0;j<n;j++) 82 time[i][j]=MAX; 83 ans=MAX; 84 bfs(); 85 if(ans<=tmp){ 86 printf("yes\n"); 87 } 88 else 89 printf("no\n"); 90 } 91 return 0; 92 }