AGC033A - Marginalia

TLE のコード

H, W = gets.split.map(&:to_i)
$field = H.times.map {gets.chomp}

Area = W * H

class Step
  @@count = 0
  @@max_step = 0

  def initialize(x, y, step = 0)
    @x = x
    @y = y
    @step = step

    @@count += 1
    @@max_step = step if step > @@max_step
  end

  def dir(i)
    dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][i]
    x = @x + dx
    y = @y + dy
    if x < 0 || x >= W || y < 0 || y >= H
      nil
    else
      ($field[y][x] == ".") ? Step.new(x, y, @step + 1) : nil
    end
  end

  def set
    $field[@y][@x] = "#"
    self
  end

  def self.last?
    @@count >= Area
  end

  def self.number
    @@max_step
  end
end


q = []

H.times do |y|
  W.times {|x| q << Step.new(x, y) if $field[y][x] == "#"}
end

until Step.last?
  now = q.shift
  4.times do |i|
    nxt = now.dir(i)
    q << nxt.set if nxt
  end
end

puts Step.number

Pythonコードの例

https://atcoder.jp/contests/agc033/submissions/12504219
numpyを使っている。

import numpy as np
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
field=[[0 if field[j][i]=='#' else h+w for i in range(w)]for j in range(h)]
field=np.array(field)
for i in range(1,h):
  field[i,:]=np.minimum(field[i,:],field[i-1,:]+1)
for i in range(h-1,0,-1):
  field[i-1,:]=np.minimum(field[i,:]+1,field[i-1,:])
for i in range(1,w):
  field[:,i]=np.minimum(field[:,i],field[:,i-1]+1)
for i in range(w-1,0,-1):
  field[:,i-1]=np.minimum(field[:,i]+1,field[:,i-1])
print(np.max(field))

NArrayを使って移植

require "numo/narray"
include Numo

h, w = gets.split.map(&:to_i)
a = h.times.map {gets.chomp.chars.map {|e| e == "#" ? 0 : h + w}}

field = Int16.cast(a)

1.upto(h - 1) do |i|
  a = field[i, true]
  b = field[i - 1, true] + 1
  a[a > b] = b[a > b]
end

(h - 1).downto(1) do |i|
  a = field[i, true] + 1
  b = field[i - 1, true]
  b[a < b] = a[a < b]
end

1.upto(w - 1) do |i|
  a = field[true, i]
  b = field[true, i - 1] + 1
  a[a > b] = b[a > b]
end

(w - 1).downto(1) do |i|
  a = field[true, i] + 1
  b = field[true, i - 1]
  b[a < b] = a[a < b]
end

puts field.max

a[a > b] = b[a > b]は、aでbより大きいところをbで置き換える（aとbの小さい方がaに入る）。これはビューなので、もとのfieldも変化する。

※参考
NArrayの簡単なつかい方 - Qiita
Numo::NArray Overview (Japanese) · ruby-numo/numo-narray Wiki · GitHub