hdu 5067 网络赛状态压缩或dfs

题意是给你n*m的方格里面有最多10个格子有数问你最少走多少步能将所有的数字移到左上角能无限装下数字

这里介绍两种做法 dfs和状态压缩dp

1 dfs

由于每个数字之间是一定可以到达的所有只用考虑走有数字的情况最多10！种情况找到做小的就行果断的深搜注意下优化

#include
  
   
#include
   
     #include
     
     using namespace std
     ; struct node
      { int x
     ,y
     ; }leap
     [20
     ]; int abs
     (int a
     ) { return a
     <0
     ?-a
     :a
     ; } int map
     [55
     ][55
     ],k
     ,Min
     ,visit
     [20
     ]; int dfs
     (int step
     ,int num
     ,int x
     ,int y
     ) { int i
     ; if(step
     >Min
     ) return 0
     ; if(num
     ==k
     ) { if(step
     +x
     -1
     +y
     -1
     <Min
     ) Min
     =step
     +x
     -1
     +y
     -1
     ; return 0
     ; } for(i
     =1
     ;i
     <=k
     ;i
     ++) { if(visit
     [i
     ]) continue; visit
     [i
     ]=1
     ; dfs
     (step
     +abs
     (leap
     [i
     ].x
     -x
     )+abs
     (leap
     [i
     ].y
     -y
     ),num
     +1
     ,leap
     [i
     ].x
     ,leap
     [i
     ].y
     ); visit
     [i
     ]=0
     ; } return 0
     ; } int main() { int i
     ,j
     ,n
     ,m
     ; while(~scanf
     ("%d%d"
     ,&n
     ,&m
     )) { k
     =0
     ; for(i
     =1
     ;i
     <=n
     ;i
     ++) for(j
     =1
     ;j
     <=m
     ;j
     ++) { scanf
     ("%d"
     ,&map
     [i
     ][j
     ]); if(map
     [i
     ][j
     ]) { leap
     [++k
     ].x
     =i
     ; leap
     [k
     ].y
     =j
     ; } } Min
     =99999999
     ; memset
     (visit
     ,0
     ,sizeof(visit
     )); dfs
     (0
     ,0
     ,1
     ,1
     ); if(k
     ==0
     ) printf
     ("0\n"
     ); else printf
     ("%d\n"
     ,Min
     ); } return 0
     ; }

2 状态压缩dp

这里的点只针对有数字的点

共10种状态 dp【i】【j】表示状态i里走到j这个点的最少步数 dis表示每个点之间所需要的步数

#include
  
   
#include
   
     #include
     
     using namespace std
     ; #define INF 0x3f3f3f3f 
      int min
     (int a
     ,int b
     ) { return a
     <b
     ?a
     :b
     ; } struct node
      { int x
     ,y
     ; }leap
     [15
     ]; int abs
     (int a
     ) { return a
     <0
     ?-a
     :a
     ; } int cont
     (int a
     , int b
     ) { return abs
     (leap
     [a
     ].x
     -leap
     [b
     ].x
     )+abs
     (leap
     [a
     ].y
     -leap
     [b
     ].y
     ); } int dp
     [5000
     ][15
     ]; int main() { int i
     ,j
     ,n
     ,m
     ,a
     ; while(~scanf
     ("%d%d"
     ,&n
     ,&m
     )) { int k
     =0
     ; for(i
     =1
     ;i
     <=n
     ;i
     ++) for(j
     =1
     ;j
     <=m
     ;j
     ++) { scanf
     ("%d"
     ,&a
     ); if(a
     ) { leap
     [++k
     ].x
     =i
     ; leap
     [k
     ].y
     =j
     ; } } leap
     [0
     ].x
     =leap
     [0
     ].y
     =1
     ; int state
     =1
     <<(k
     +1
     ); memset
     (dp
     ,INF
     ,sizeof(dp
     )); int dis
     [15
     ][15
     ]; for(i
     =0
     ;i
     <=k
     ;i
     ++) for(j
     =i
     ;j
     <=k
     ;j
     ++) dis
     [i
     ][j
     ]=dis
     [j
     ][i
     ]=cont
     (i
     ,j
     ); dp
     [1
     ][0
     ]=0
     ; for(i
     =1
     ;i
     <state
     ;i
     ++) { for(j
     =0
     ;j
     <=k
     ;j
     ++) { if(dp
     [i
     ][j
     ]==INF
     ) continue; for(int z
     =0
     ;z
     <=k
     ;z
     ++) { if(i
     &(1
     <<z
     )) continue; dp
     [i
     |(1
     <<z
     )][z
     ]=min
     (dp
     [i
     |(1
     <<z
     )][z
     ],dp
     [i
     ][j
     ]+dis
     [j
     ][z
     ]); } } } int Min
     =9999999
     ; for(i
     =0
     ;i
     <=k
     ;i
     ++) if(dp
     [state
     -1
     ][i
     ]+dis
     [i
     ][0
     ]<Min
     ) Min
     =dp
     [state
     -1
     ][i
     ]+dis
     [i
     ][0
     ]; printf
     ("%d\n"
     ,Min
     ); } return 0
     ; }

hdu 5067 网络赛 状态压缩 或dfs