読者です 読者をやめる 読者になる 読者になる

「人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題」競技コーダでもアルゴリズマでもない自分が解いてみた

人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題

これを解こうとしたのだけど、まったくできる気がしなくて、結局

http://d.hatena.ne.jp/kusano_prog/20100111/1263199194

ここのRubyへのportをつくった。それでも手こずり3時間かかった。
なんとか作り終えて
「この会社はアルゴリズマか競技コーダを求めているんだろうな」
と思いました。

今までの募集記事を見る限りでは、特に「アルゴリズムに強い人募集」などと書かれている様子は無かったので。今度からしっかりと明記すればもっと良い人材が集まるのではないかと。

俺はこの会社には入れないようです。

#http://okajima.air-nifty.com/b/2010/01/post-abc6.html

map = ARGF.readlines
map.each{|line| line.chomp!}
sizeY = map.size
sizeX = map[0].size
size = sizeY * sizeX

startX=startY=goalX=goalY=0

sizeY.times do |y|
  sizeX.times do |x|
    if map[y][x, 1] == 'S'
      startX = x
      startY = y
    elsif map[y][x, 1] == 'G'
      goalX = x
      goalY = y
    end
  end
end

dist = (0..sizeY).map do |y|
  (0..sizeX).map do |x|
    [size, nil]
  end
end
dist[startY][startX] = [0, nil]

pp startX, startY, goalX, goalY
p sizeX, sizeY, size

size.times do |i|
  break if dist[goalY][goalX][0] < size
  sizeY.times do |y|
    sizeX.times do |x|
      if dist[y][x][0] == i
        4.times do |d|
          tx = x+[1, 0, -1, 0][d]
          ty = y+[0, 1, 0, -1][d]
          if (0<=tx and tx<sizeX and 0<=ty and ty<sizeY and
              map[ty][tx, 1] != '*' and
              dist[ty][tx][0] == size)
            dist[ty][tx] = [i+1, [x, y]]
          end
        end
      end
    end
  end
end

x = dist[goalY][goalX][1][0]
y = dist[goalY][goalX][1][1]
until [x, y] == [startX, startY]
  p [x, y]
  map[y][x] = '$'
  x = dist[y][x][1][0]
  y = dist[y][x][1][1]
end
puts map.join("\n")