hdu 4528 马拉松不错的广搜

思路： 每个地方能走多次 所以得记录状态 把大明记为1 二明记为2所以状态里最多有4种状态（0，1，2，3） 对每一点 每个状态只能走一次 判断能不能看到 直接根据坐标判断 如果x相等 判断之间有没有墙和人 其他思路同一般广搜

#include
  
   
#include
   
     #include
    
      #include
      
      using namespace std
      ; int n
      ,m
      ,mark
      [110
      ][110
      ][10
      ]; char map
      [110
      ][110
      ]; int dir
      [4
      ][2
      ]={0
      ,1
      ,0
      ,-1
      ,1
      ,0
      ,-1
      ,0
      }; int dx
      ,dy
      ,ex
      ,ey
      ,tt
      ; struct node
       { int x
      ,y
      ; int step
      ; int state
      ; }a
      ,b
      ; int min
      (int x
      ,int y
      ) { return x
      <y
      ?x
      :y
      ; } int max
      (int x
      ,int y
      ) { return x
      >y
      ?x
      :y
      ; } int judge
      (node p
      ) { int i
      ,j
      ; int cont
      =0
      ; int flash
      =0
      ; if(p
      .x
      ==dx
      ) { for(i
      =min
      (p
      .y
      ,dy
      )+1
      ;i
      <max
      (p
      .y
      ,dy
      );i
      ++) { if(map
      [dx
      ][i
      ]=='X'
      ||dx
      ==ex
      &&i
      ==ey
      ) {flash
      =1
      ;break;} } if(flash
      ==0
      ) cont
      +=map
      [dx
      ][dy
      ]-'0'
      ; } flash
      =0
      ; if(p
      .y
      ==dy
      ) { for(i
      =min
      (p
      .x
      ,dx
      )+1
      ;i
      <max
      (p
      .x
      ,dx
      );i
      ++) { if(map
      [i
      ][dy
      ]=='X'
      ||dy
      ==ey
      &&i
      ==ex
      ) { flash
      =1
      ; break; } } if(flash
      ==0
      ) cont
      +=map
      [dx
      ][dy
      ]-'0'
      ; } flash
      =0
      ; if(p
      .x
      ==ex
      ) { for(i
      =min
      (p
      .y
      ,ey
      )+1
      ;i
      <max
      (p
      .y
      ,ey
      );i
      ++) { if(map
      [ex
      ][i
      ]=='X'
      ||ex
      ==dx
      &&i
      ==dy
      ) {flash
      =1
      ;break;} } if(flash
      ==0
      ) cont
      +=map
      [ex
      ][ey
      ]-'0'
      ; } flash
      =0
      ; if(p
      .y
      ==ey
      ) { for(i
      =min
      (p
      .x
      ,ex
      )+1
      ;i
      <max
      (p
      .x
      ,ex
      );i
      ++) { if(map
      [i
      ][ey
      ]=='X'
      ||ey
      ==dy
      &&i
      ==dx
      ) { flash
      =1
      ; break; } } if(flash
      ==0
      ) cont
      +=map
      [ex
      ][ey
      ]-'0'
      ; } return cont
      ; } int bfs
      (int xi
      ,int xj
      ) { int i
      ; memset
      (mark
      ,0
      ,sizeof(mark
      )); a
      .x
      =xi
      ; a
      .y
      =xj
      ; a
      .state
      =judge
      (a
      ); a
      .step
      =0
      ; queue
      <node
      >q
      ; mark
      [a
      .x
      ][a
      .y
      ][a
      .state
      ]=1
      ; q
      .push
      (a
      ); int flash
      =0
      ; while(!q
      .empty
      ()) { b
      =q
      .front
      (); q
      .pop
      (); if(b
      .state
      ==3
      ) { flash
      =1
      ; printf
      ("%d\n"
      ,b
      .step
      ); break; } for(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
      ]=='1'
      ||map
      [a
      .x
      ][a
      .y
      ]=='2'
      ) continue; if(map
      [a
      .x
      ][a
      .y
      ]=='X'
      ) continue; if(a
      .step
      >tt
      ) continue; a
      .state
      =b
      .state
      ; int t
      =judge
      (a
      ); if(t
      ==3
      ) a
      .state
      =t
      ; else if(t
      ==2
      ) { if(a
      .state
      !=2
      ) a
      .state
      +=t
      ; } else if(t
      ==1
      ) { if(a
      .state
      !=1
      ) a
      .state
      +=t
      ; } if(mark
      [a
      .x
      ][a
      .y
      ][a
      .state
      ]==0
      ) { mark
      [a
      .x
      ][a
      .y
      ][a
      .state
      ]=1
      ; q
      .push
      (a
      ); } } } if(flash
      ==0
      ) printf
      ("-1\n"
      ); return 0
      ; } int main() { int i
      ,j
      ,T
      ,d
      =1
      ; scanf
      ("%d"
      ,&T
      ); while(T
      --) { scanf
      ("%d%d%d"
      ,&n
      ,&m
      ,&tt
      ); for(i
      =0
      ;i
      <n
      ;i
      ++) scanf
      ("%s"
      ,map
      [i
      ]); int xi
      ,xj
      ; for(i
      =0
      ;i
      <n
      ;i
      ++) for(j
      =0
      ;j
      <m
      ;j
      ++) { if(map
      [i
      ][j
      ]=='D'
      ) { map
      [i
      ][j
      ]='1'
      ; dx
      =i
      ; dy
      =j
      ; } else if(map
      [i
      ][j
      ]=='E'
      ) { map
      [i
      ][j
      ]='2'
      ; ex
      =i
      ; ey
      =j
      ; } else if(map
      [i
      ][j
      ]=='S'
      ) { xi
      =i
      ; xj
      =j
      ; } } //printf("%d^^^^%d\n",xi,xj); printf
      ("Case %d:\n"
      ,d
      ++); bfs
      (xi
      ,xj
      ); } return 0
      ; }