#1501029

Solution for 0223: Stray Twins by iwamot

Source Code Status Test Cases
    Policy: public     Reviewed: 97    
07.71 sec    36404 KB    55 lines     1226 bytes    2015-09-03 00:32
def bfs(x, y, tx, ty, kx, ky, depart)
  return 0 if tx == kx && ty == ky

  memo = {"#{tx},#{ty},#{kx},#{ky}" => 0}
  q = [[tx, ty, kx, ky]]

  mv = [[-1, 0], [1, 0], [0, -1], [0, 1]]

  until q.empty?
    tx, ty, kx, ky = q.shift

    n = memo["#{tx},#{ty},#{kx},#{ky}"]
    return 'NA' if n >= 100

    mv.each do |mx, my|
      txn = tx + mx
      tyn = ty + my
      kxn = kx - mx
      kyn = ky - my
      if mx != 0
        txn = tx if txn < 0 || txn >= x || depart[tyn][txn] == 1
        kxn = kx if kxn < 0 || kxn >= x || depart[kyn][kxn] == 1
      else
        tyn = ty if tyn < 0 || tyn >= y || depart[tyn][txn] == 1
        kyn = ky if kyn < 0 || kyn >= y || depart[kyn][kxn] == 1
      end

      return n + 1 if txn == kxn && tyn == kyn

      key = "#{txn},#{tyn},#{kxn},#{kyn}"
      next if memo[key]

      memo[key] = n + 1
      q.push [txn, tyn, kxn, kyn]
    end
  end

  'NA'
end

while true
  x, y = gets.chomp.split(' ').map(&:to_i)
  break if x == 0 && y == 0

  tx, ty = gets.chomp.split(' ').map(&:to_i)
  kx, ky = gets.chomp.split(' ').map(&:to_i)

  depart = []
  y.times do |i|
    depart[i] = gets.chomp.split(' ').map(&:to_i)
  end
  puts bfs(x, y, tx - 1, ty - 1, kx - 1, ky - 1, depart)
end


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 1/1 Ruby CPU: 07.71 sec Memory: 36404 KB Length: 1226 B 2015-09-03 00:32 2015-09-03 00:32
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 07.71 sec 36404 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags