hdu 3533 搜索+预处理

题意是给你一个地图，地图里有的点是炮台 炮台每隔一段时间回想固定的方向发射一定速度的炮弹，炮弹不能穿过炮台，炮弹只有只有在整点才能打中人，开始你在（0,0）的位置 问你能不能再规定的时间内走到终点；

最对100个炮台，最多走1000步 很明显 把地图预先处理下 及每个点在某一时间有炮弹 那么人就不能走， 开个3维 来标记，还有 数组必须用bool型的要不然要超类存，

?

?

#include
  
   
#include
   
     #include
    
      #include
      
      using namespace std
      ; int n
      ,m
      ,k
      ,d
      ; bool map
      [101
      ][101
      ][1001
      ]; bool mark
      [101
      ][101
      ][1001
      ]; struct node
       { int x
      ,y
      ; int tt
      ; }a
      ,b
      ; struct Node
       { int dir
      ; int x
      ,y
      ; int t
      ,v
      ; }bull
      [110
      ]; int dir1
      [4
      ][2
      ]={-1
      ,0
      ,0
      ,1
      ,1
      ,0
      ,0
      ,-1
      }; int dir
      [5
      ][2
      ]={0
      ,0
      ,0
      ,1
      ,0
      ,-1
      ,1
      ,0
      ,-1
      ,0
      }; int deal
      (int x
      ) { int i
      ,j
      ; int di
      =bull
      [x
      ].dir
      ; int xx
      ,yy
      ; for(i
      =1
      ;;i
      ++) { xx
      =bull
      [x
      ].x
      +i
      *dir1
      [di
      ][0
      ]*bull
      [x
      ].v
      ; yy
      =bull
      [x
      ].y
      +i
      *dir1
      [di
      ][1
      ]*bull
      [x
      ].v
      ; if(xx
      <0
      ||xx
      >n
      ||yy
      <0
      ||yy
      >m
      ) break; if(map
      [xx
      ][yy
      ][0
      ]) break; int flag
      =0
      ; if(di
      ==0
      ) { for(j
      =xx
      ;j
      <bull
      [x
      ].x
      ;j
      ++) if(map
      [j
      ][bull
      [x
      ].y
      ][0
      ]) {flag
      =1
      ;break;} } else if(di
      ==1
      ) { for(j
      =bull
      [x
      ].y
      +1
      ;j
      <=yy
      ;j
      ++) if(map
      [bull
      [x
      ].x
      ][j
      ][0
      ]) {flag
      =1
      ;break;} } else if(di
      ==2
      ) { for(j
      =bull
      [x
      ].x
      +1
      ;j
      <=xx
      ;j
      ++) if(map
      [j
      ][bull
      [x
      ].y
      ][0
      ]){flag
      =1
      ;break;} } else if(di
      ==3
      ) { for(j
      =yy
      ;j
      <bull
      [x
      ].y
      ;j
      ++) if(map
      [bull
      [x
      ].x
      ][j
      ][0
      ]) {flag
      =1
      ;break;} } if(flag
      ) break; j
      =0
      ; int t
      =i
      ; while(t
      <=d
      ) { map
      [xx
      ][yy
      ][t
      ]=1
      ; j
      ++; t
      =i
      +j
      *bull
      [x
      ].t
      ; } } return 0
      ; } int bfs
      () { a
      .x
      =0
      ; a
      .y
      =0
      ; a
      .tt
      =0
      ; memset
      (mark
      ,0
      ,sizeof(mark
      )); queue
      <node
      >q
      ; mark
      [a
      .x
      ][a
      .y
      ][a
      .tt
      ]=1
      ; q
      .push
      (a
      ); int i
      ,j
      ; int flash
      =0
      ; while(!q
      .empty
      ()) { b
      =q
      .front
      (); q
      .pop
      (); //printf("%d %d\n",b.x,b.y); 
       if(b
      .x
      ==n
      &&b
      .y
      ==m
      ) { printf
      ("%d\n"
      ,b
      .tt
      ); flash
      =1
      ; break; } for(i
      =0
      ;i
      <5
      ;i
      ++) { a
      .x
      =b
      .x
      +dir
      [i
      ][0
      ]; a
      .y
      =b
      .y
      +dir
      [i
      ][1
      ]; a
      .tt
      =b
      .tt
      +1
      ; if(n
      -a
      .x
      +m
      -a
      .y
      >d
      -a
      .tt
      ) continue; if(a
      .x
      <0
      ||a
      .x
      >n
      ||a
      .y
      <0
      ||a
      .y
      >m
      ) continue; if(map
      [a
      .x
      ][a
      .y
      ][0
      ]) continue; if(map
      [a
      .x
      ][a
      .y
      ][a
      .tt
      ]==0
      &&mark
      [a
      .x
      ][a
      .y
      ][a
      .tt
      ]==0
      ) { mark
      [a
      .x
      ][a
      .y
      ][a
      .tt
      ]=1
      ; q
      .push
      (a
      ); } } } if(!flash
      ) printf
      ("Bad luck!\n"
      ); return 0
      ; } int main() { int i
      ,j
      ; while(~scanf
      ("%d%d%d%d"
      ,&n
      ,&m
      ,&k
      ,&d
      )) { char str
      [2
      ]; memset
      (map
      ,0
      ,sizeof(map
      )); for(i
      =1
      ;i
      <=k
      ;i
      ++) { scanf
      ("%s"
      ,str
      ); if(str
      [0
      ]=='N'
      ) bull
      [i
      ].dir
      =0
      ; else if(str
      [0
      ]=='E'
      ) bull
      [i
      ].dir
      =1
      ; else if(str
      [0
      ]=='S'
      ) bull
      [i
      ].dir
      =2
      ; else if(str
      [0
      ]=='W'
      )bull
      [i
      ].dir
      =3
      ; scanf
      ("%d%d"
      ,&bull
      [i
      ].t
      ,&bull
      [i
      ].v
      ); scanf
      ("%d%d"
      ,&bull
      [i
      ].x
      ,&bull
      [i
      ].y
      ); map
      [bull
      [i
      ].x
      ][bull
      [i
      ].y
      ][0
      ]=1
      ; } for(i
      =1
      ;i
      <=k
      ;i
      ++) { deal
      (i
      ); } bfs
      (); } return 0
      ; } 
     
    
   
  

?