hdu 4771 状态压缩搜索

基本上和胜利大逃亡一样！！！！！！！！

#include
  
   
#include
   
     #include
    
      #include
      
      using namespace std
      ; int mark
      [110
      ][110
      ][1
      <<6
      ],n
      ,m
      ; char map
      [110
      ][110
      ]; int leap
      [110
      ][110
      ]; struct node
       { int x
      ,y
      ,step
      ; int state
      ; int cont
      ; }a
      ,b
      ; int dir
      [4
      ][2
      ]={-1
      ,0
      ,0
      ,1
      ,0
      ,-1
      ,1
      ,0
      }; int bfs
      (int x
      ,int y
      ,int num
      ) { queue
      <node
      >q
      ; a
      .x
      =x
      ; a
      .y
      =y
      ; a
      .step
      =0
      ; a
      .state
      =0
      ; a
      .cont
      =0
      ; if(leap
      [x
      ][y
      ]) { a
      .state
      =(1
      <<leap
      [x
      ][y
      ]); a
      .cont
      =1
      ; } memset
      (mark
      ,0
      ,sizeof(mark
      )); mark
      [a
      .x
      ][a
      .y
      ][a
      .state
      ]=1
      ; q
      .push
      (a
      ); int flash
      =0
      ; while(!q
      .empty
      ()) { b
      =q
      .front
      (); q
      .pop
      (); if(b
      .cont
      ==num
      ) { printf
      ("%d\n"
      ,b
      .step
      ); flash
      =1
      ; break; } for(int i
      =0
      ;i
      <4
      ;i
      ++) { a
      .x
      =b
      .x
      +dir
      [i
      ][0
      ]; a
      .y
      =b
      .y
      +dir
      [i
      ][1
      ]; a
      .step
      =b
      .step
      +1
      ; if(a
      .x
      <0
      ||a
      .x
      >=n
      ||a
      .y
      <0
      ||a
      .y
      >=m
      ) continue; if(map
      [a
      .x
      ][a
      .y
      ]=='#'
      ) continue; if(leap
      [a
      .x
      ][a
      .y
      ]) { if((b
      .state
      &(1
      <<leap
      [a
      .x
      ][a
      .y
      ]))==0
      ) a
      .cont
      =b
      .cont
      +1
      ; else a
      .cont
      =b
      .cont
      ; a
      .state
      =b
      .state
      |(1
      <<leap
      [a
      .x
      ][a
      .y
      ]); } else { a
      .state
      =b
      .state
      ; a
      .cont
      =b
      .cont
      ; } if(mark
      [a
      .x
      ][a
      .y
      ][a
      .state
      ]==0
      ) { mark
      [a
      .x
      ][a
      .y
      ][a
      .state
      ]=1
      ; q
      .push
      (a
      ); } } } if(!flash
      ) printf
      ("-1\n"
      ); return 0
      ; } int main() { int i
      ,j
      ,a
      ,b
      ; while(~scanf
      ("%d%d"
      ,&n
      ,&m
      )) { if(n
      +m
      ==0
      ) break; for(i
      =0
      ;i
      <n
      ;i
      ++) scanf
      ("%s"
      ,map
      [i
      ]); int s
      ; scanf
      ("%d"
      ,&s
      ); memset
      (leap
      ,0
      ,sizeof(leap
      )); j
      =0
      ; for(i
      =1
      ;i
      <=s
      ;i
      ++) { scanf
      ("%d%d"
      ,&a
      ,&b
      ); leap
      [a
      -1
      ][b
      -1
      ]=++j
      ; } int x
      ,y
      ; for(i
      =0
      ;i
      <n
      ;i
      ++) for(j
      =0
      ;j
      <m
      ;j
      ++) if(map
      [i
      ][j
      ]=='@'
      ) { x
      =i
      ; y
      =j
      ; } bfs
      (x
      ,y
      ,s
      ); } return 0
      ; }