hdu 4230 bfs+记忆化搜索

告诉你从起点到终点最短步数的方式有多少种；

mark表示每个点对应每个方向的最小步数；

num表示种树；

然后按照题意搜就行

#include
  
   
#include
   
     #include
    
      #include
      
      using namespace std
      ; #define INF 0x3f3f3f3f 
      struct node
       { int x
      ,y
      ,step
      ; int d
      ; }a
      ,b
      ; int n
      ,m
      ; char map
      [110
      ][110
      ]; int mark
      [110
      ][110
      ][5
      ]; int num
      [110
      ][110
      ][5
      ]; int dir
      [4
      ][2
      ]={-1
      ,0
      ,0
      ,1
      ,1
      ,0
      ,0
      ,-1
      }; queue
      <node
      >q
      ; int deal
      (node next
      ,node cur
      ) { if(next
      .step
      <mark
      [next
      .x
      ][next
      .y
      ][next
      .d
      ]) { mark
      [next
      .x
      ][next
      .y
      ][next
      .d
      ]=next
      .step
      ; num
      [next
      .x
      ][next
      .y
      ][next
      .d
      ]=num
      [cur
      .x
      ][cur
      .y
      ][cur
      .d
      ]; num
      [next
      .x
      ][next
      .y
      ][next
      .d
      ]%=1000000
      ; q
      .push
      (next
      ); } else if(next
      .step
      ==mark
      [next
      .x
      ][next
      .y
      ][next
      .d
      ]) { num
      [next
      .x
      ][next
      .y
      ][next
      .d
      ]+=num
      [cur
      .x
      ][cur
      .y
      ][cur
      .d
      ]; num
      [next
      .x
      ][next
      .y
      ][next
      .d
      ]%=1000000
      ; } return 0
      ; } int bfs
      (int x
      ,int y
      ,int d
      ) { memset
      (mark
      ,INF
      ,sizeof(mark
      )); memset
      (num
      ,0
      ,sizeof(num
      )); a
      .x
      =x
      ; a
      .y
      =y
      ; a
      .step
      =0
      ; a
      .d
      =d
      ; mark
      [a
      .x
      ][a
      .y
      ][a
      .d
      ]=0
      ; num
      [a
      .x
      ][a
      .y
      ][a
      .d
      ]=1
      ; //queue
      
       q; q
       .push
       (a
       ); while(!q
       .empty
       ()) { b
       =q
       .front
       (); q
       .pop
       (); a
       =b
       ; if(b
       .d
       ==1
       ) a
       .d
       =4
       ; else if(b
       .d
       ==2
       ) a
       .d
       =1
       ; else if(b
       .d
       ==3
       ) a
       .d
       =2
       ; else if(b
       .d
       ==4
       ) a
       .d
       =3
       ; a
       .step
       =b
       .step
       +1
       ; deal
       (a
       ,b
       ); a
       =b
       ; if(b
       .d
       ==1
       ) a
       .d
       =2
       ; else if(b
       .d
       ==2
       ) a
       .d
       =3
       ; else if(b
       .d
       ==3
       ) a
       .d
       =4
       ; else if(b
       .d
       ==4
       ) a
       .d
       =1
       ; a
       .step
       =b
       .step
       +1
       ; deal
       (a
       ,b
       ); for(int i
       =1
       ;;i
       ++) { a
       .x
       =b
       .x
       +i
       *dir
       [b
       .d
       -1
       ][0
       ]; a
       .y
       =b
       .y
       +i
       *dir
       [b
       .d
       -1
       ][1
       ]; a
       .step
       =b
       .step
       +1
       ; a
       .d
       =b
       .d
       ; if(a
       .x
       <0
       ||a
       .x
       >=n
       ||a
       .y
       <0
       ||a
       .y
       >=m
       ) break; if(map
       [a
       .x
       ][a
       .y
       ]=='*'
       ) break; deal
       (a
       ,b
       ); } } return 0
       ; } int main() { int i
       ,j
       ; while(~scanf
       ("%d%d"
       ,&n
       ,&m
       )) { if(n
       ==0
       &&m
       ==0
       ) break; for(i
       =0
       ;i
       <n
       ;i
       ++) scanf
       ("%s"
       ,map
       [i
       ]); int ex
       ,ey
       ; for(i
       =0
       ;i
       <n
       ;i
       ++) { for(j
       =0
       ;j
       <m
       ;j
       ++) { if(map
       [i
       ][j
       ]=='N'
       ) bfs
       (i
       ,j
       ,1
       ); else if(map
       [i
       ][j
       ]=='E'
       ) bfs
       (i
       ,j
       ,2
       ); else if(map
       [i
       ][j
       ]=='S'
       ) bfs
       (i
       ,j
       ,3
       ); else if(map
       [i
       ][j
       ]=='W'
       ) bfs
       (i
       ,j
       ,4
       ); else if(map
       [i
       ][j
       ]=='X'
       ) { ex
       =i
       ; ey
       =j
       ; } } } int Min
       =INF
       ; for(i
       =0
       ;i
       <=4
       ;i
       ++) if(mark
       [ex
       ][ey
       ][i
       ]<Min
       ) Min
       =mark
       [ex
       ][ey
       ][i
       ]; int t
       =0
       ; for(i
       =1
       ;i
       <=4
       ;i
       ++) if(mark
       [ex
       ][ey
       ][i
       ]==Min
       ) t
       +=num
       [ex
       ][ey
       ][i
       ]; if(Min
       ==INF
       ) printf
       ("0 0\n"
       ); else printf
       ("%d %d\n"
       ,Min
       ,t
       %1000000
       ); } return 0
       ; }