- 论坛徽章:
- 0
|
前几天看到hdu 1195:
Now an emergent task for you is to open a password lock. The password is consisted of four digits. Each digit is numbered from 1 to 9.
Each time, you can add or minus 1 to any digit. When add 1 to '9', the digit will change to be '1' and when minus 1 to '1', the digit will change to be '9'. You can also exchange the digit with its neighbor. Each action will take one step.
Now your task is to use minimal steps to open the lock.
Note: The leftmost digit is not the neighbor of the rightmost digit.
我用如下代码解,其中用到了两个假设:
1. 对于给定操作步骤,操作顺序可以打乱。(将各位编号,交换同时交换编号,增减操作绑定编号)
2. 对于可通过纯交换实现的变化,则最少交换步骤等同于将源组合冒泡排序至目标组合。
calculate函数求解,参数为 源状态 终状态,结果为 (最少步数, _)- import Data.Maybe
- import Data.List
- steps4Exchange :: [ Int ] -> Int
- steps4Exchange dst =
- snd $ iterate swapPass (dst, 0) !! (length dst - 1)
- where swapPass ([ x ], i) = ([ x ], i)
- swapPass (x : y : zs, i)
- | x > y =
- let (xs, i') = swapPass (x : zs, i + 1) in
- (y : xs, i')
- | otherwise =
- let (xs, i') = swapPass (y : zs, i) in
- (x : xs, i')
- steps4Move :: [ Int ] -> [ Int ] -> Int
- steps4Move src dst =
- sum $ map (\(s, i) ->
- let d = dst !! i in
- min (abs (d - s)) (9 + s - d)
- ) $ zip src [ 0 .. ]
- calculate :: [ Int ] -> [ Int ] -> (Int, [ Int ])
- calculate src dst =
- let src' = zip src [ 0 .. ] in
- foldl1 (\(a, a') (b, b') ->
- if a > b then
- (b, b')
- else
- (a, a')
- ) $ map (\mid' ->
- let mid = fst $ unzip mid' in
- (steps4Exchange (snd $ unzip mid') + steps4Move mid dst, mid)
- ) $ permutations src'
复制代码 |
|