fork download 
  1. "Squeak/Pharo Smalltalk
  2.  
  3. お題
  4. N×Mのフィールドが与えられる。各マスの意味は以下の通りとする。
  5. 'S'：始点
  6. 'G'：終点
  7. '.'：通行可
  8. '#'：通行不可
  9.  
  10. 連続して同じ方向に進むことができないという制約下で、
  11. 始点から終点までの最短距離を求めよ。
  12.  
  13. [example 1]
  14. 'S....
  15. #....
  16. ..#..
  17. ....G'
  18. => 9
  19.  
  20. [example 2]
  21. 'S.....G
  22. .......'
  23. => 12
  24.  
  25. "
  26.  
  27. | solve |
  28.  
  29. solve := [:map |
  30.    | N M memo defaultDict goal fromDirs pos queue |
  31.    N := map lines size.
  32.    M := map lines first size.
  33.    memo := Matrix rows: N columns: M contents: (map asArray copyWithout: Character cr).
  34.    fromDirs := (0@0) fourNeighbors.
  35.    defaultDict := (fromDirs collect: [:dir | dir -> Float infinity]) as: Dictionary.
  36.    memo replaceAll: $. with: defaultDict.
  37.    memo := memo deepCopy.
  38.    goal := memo indexOf: $G.
  39.    memo at: goal x at: goal y put: defaultDict copy.
  40.    pos := memo indexOf: $S.
  41.    memo at: pos x at: pos y put: ((fromDirs collect: [:dir | dir -> 0]) as: Dictionary).
  42.    queue := OrderedCollection withAll: (fromDirs collect: [:dir | dir -> pos]).
  43.    [queue isEmpty] whileFalse: [
  44.       | assoc dist |
  45.       assoc := queue removeFirst.
  46.       pos := assoc value.
  47.       dist := ((memo at: pos x at: pos y) at: assoc key) + 1.
  48.       (fromDirs copyWithout: assoc key) do: [:dir | [:exit |
  49.          | next dict |
  50.          next := pos + dir.
  51.          (dict := memo at: next x at: next y ifInvalid: $#) isDictionary ifFalse: [exit value].
  52.          (dict at: dir) > dist ifTrue: [
  53.             dict at: dir put: dist.
  54.             next = goal ifFalse: [queue add: dir -> next]
  55.          ]
  56.       ] valueWithExit]
  57.    ].
  58.    (memo at: goal x at: goal y) values min
  59. ].
  60.  
  61. solve value: 
  62. 'S....
  63. #....
  64. ..#..
  65. ....G'. "=> 9 "
  66.  
  67. solve value: 
  68. 'S.....G
  69. .......'. "=> 12 "
  70.  
  71. solve value: 
  72. 'S.#G
  73. ....'. "=> Infinity "
  74.  
  75. solve value: 
  76. '#.#.#
  77. S...G
  78. ##.#.'. "=> 10 "
  79.  
  80. solve value: 
  81. 'S#G'. "=> Infinity "
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ACAeKW
language:
Text (text 6.10)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!