hdu1428 记忆化搜索

注意：

题目给的是你每个点的值 所以必须的先求出来每个点到终点的最小路径和 这里我是用bfs处理的 存在dis数组里

注意题意里说的 当前这个点能走到下个点的条件是当前点到终点的值比下个点到终点的值大

#include
  
   
#include
   
     #include
    
      #include
      
      using namespace std
      ; #define INF 0x3f3f3f3f 
       __int64 dp
      [55
      ][55
      ],n
      ; int mark
      [55
      ][55
      ],tie
      [55
      ][55
      ]; int dir
      [4
      ][2
      ]={0
      ,1
      ,0
      ,-1
      ,1
      ,0
      ,-1
      ,0
      },dis
      [55
      ][55
      ]; int max
      (int a
      ,int b
      ) { return a
      >b
      ?a
      :b
      ; } int min
      (int a
      ,int b
      ) { return a
      <b
      ?a
      :b
      ; } struct node
       { int x
      ,y
      ; }a
      ,b
      ; int bfs
      () { a
      .x
      =n
      ; a
      .y
      =n
      ; queue
      <node
      >q
      ; q
      .push
      (a
      ); while(!q
      .empty
      ()) { b
      =q
      .front
      (); q
      .pop
      (); for(int i
      =0
      ;i
      <4
      ;i
      ++) { a
      .x
      =b
      .x
      +dir
      [i
      ][0
      ]; a
      .y
      =b
      .y
      +dir
      [i
      ][1
      ]; if(a
      .x
      <1
      ||a
      .x
      >n
      ||a
      .y
      <1
      ||a
      .y
      >n
      ) continue; if(dis
      [a
      .x
      ][a
      .y
      ]>dis
      [b
      .x
      ][b
      .y
      ]+tie
      [a
      .x
      ][a
      .y
      ]) { dis
      [a
      .x
      ][a
      .y
      ]=dis
      [b
      .x
      ][b
      .y
      ]+tie
      [a
      .x
      ][a
      .y
      ]; q
      .push
      (a
      ); } } } return 0
      ; } __int64 dfs
      (int x
      ,int y
      ) { int i
      ,j
      ; for(i
      =0
      ;i
      <4
      ;i
      ++) { int xx
      =x
      +dir
      [i
      ][0
      ]; int yy
      =y
      +dir
      [i
      ][1
      ]; if(xx
      <1
      ||xx
      >n
      ||yy
      <1
      ||y
      >n
      ) continue; if(dis
      [x
      ][y
      ]<=dis
      [xx
      ][yy
      ]) continue; if(mark
      [xx
      ][yy
      ]==0
      ) { mark
      [xx
      ][yy
      ]=1
      ; dfs
      (xx
      ,yy
      ); } dp
      [x
      ][y
      ]+=dp
      [xx
      ][yy
      ]; } return dp
      [x
      ][y
      ]; } int main() { int i
      ,j
      ; while(~scanf
      ("%d"
      ,&n
      )) { for(i
      =1
      ;i
      <=n
      ;i
      ++) for(j
      =1
      ;j
      <=n
      ;j
      ++) scanf
      ("%d"
      ,&tie
      [i
      ][j
      ]); memset
      (dis
      ,INF
      ,sizeof(dis
      )); dis
      [n
      ][n
      ]=tie
      [n
      ][n
      ]; bfs
      (); /*for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%d ",dis[i][j]); printf("\n"); }*/ memset
      (dp
      ,0
      ,sizeof(dp
      )); memset
      (mark
      ,0
      ,sizeof(mark
      )); mark
      [1
      ][1
      ]=1
      ; dp
      [n
      ][n
      ]=1
      ; printf
      ("%I64d\n"
      ,dfs
      (1
      ,1
      )); } return 0
      ; }