paizaの陣取りゲームでタイムオーバーになってしまう

Question

前提・実現したいこと

処理する入力数の多い問題でタイムアウトになってしまうので、これを回避したい。
newすると時間がかかると聞いたことがあるが、該当コードではどこに時間がかかっているかわからない。
該当の問題はこちら（paiza レベルアップ問題集 陣取りゲーム）

発生している問題・エラーメッセージ

テスト3以降の与られるマス目が1000*1000のものでタイムオーバーと表示されてしまう。

該当のソースコード

A = "A"
B = "B"
# 盤面
map = Array.new
# A, Bのターン数と広げた陣地を登録するキュー
a_id = 0
b_id = 0
check_map_A = Array.new
check_map_B = Array.new

# 入力される値
# H W     ・ 1 行目では、マップの行数 H , 列数 W が与えられます。
# N       ・ 2 行目では、先攻のプレイヤーの名前 N が与えられます。
# S_0     ・ 続く H 行のうち i 行目 (0 ≦ i < H) には、盤面の i 行目の文字をまとめた文字列 S_i が与えられ、 
# ...       S_i の j 文字目は、盤面の i 行目の j 列目に書かれている文字を表します。(0 ≦ j < W)
# S_(H-1)

# 与られる情報を取得
h, w = gets.chomp.split(" ").map(&:to_i)
turn = gets.chomp
h.times do
    map << gets.chomp.split("")
end

# A, Bのスタート地点を取得する
def check_start(map, turn)
    map.each_with_index do |row, row_i|
        row.each_with_index do |box, col_i|
            return {id: 0, row: row_i, col: col_i} if box == turn
        end
    end
end

# １手前に登録した座標を元に上下左右に陣地を広げる
def check_around (check_map, map, id, turn)
    # キュー(check_map)から１手前の座標を一つ取り出し、空いている上下左右のマスの座標を新たにキューに登録
    # 1手前に登録した座標がなくなるまで繰り返す
    while check_map.first[:id] == id
        box = check_map.first
        id = box[:id]
        row_i = box[:row]
        col_i = box[:col]
        check_map << {id: id + 1, row: row_i - 1, col: col_i} if map.dig(row_i - 1, col_i) == "." && row_i - 1 >= 0
        check_map << {id: id + 1, row: row_i + 1, col: col_i} if map.dig(row_i + 1, col_i) == "."
        check_map << {id: id + 1, row: row_i, col: col_i - 1} if map.dig(row_i, col_i - 1) == "." && col_i - 1 >= 0
        check_map << {id: id + 1, row: row_i, col: col_i + 1} if map.dig(row_i, col_i + 1) == "."
        check_map.shift
        return if check_map.empty?
    end
    # 新たに登録した座標にA, Bを記入する
    check_map.each do |box|
        map[box[:row]][box[:col]] = turn
    end
end

# A,Bの陣地の数を数える
def count_box(map, turn)
    count = 0
    map.each do |row|
        row.each do |box|
            if box == turn
                count += 1
            end
        end
    end
    return count
end

# A, Bのスタート地点を各キューに登録する
check_map_A << check_start(map, A)
check_map_B << check_start(map, B)

# A, Bのキューがなくなる=新たに陣地が広げられなくなるまで繰り返す
while !check_map_A.empty? || !check_map_B.empty? do
    # 各手番の陣地を広げる
    if turn == A
        check_around(check_map_A, map, a_id, A) if !check_map_A.empty?
        a_id += 1
    else
        check_around(check_map_B, map, b_id, B) if !check_map_B.empty?
        b_id += 1
    end
    # 手番を入れ替える
    turn = (turn == A)? B : A
end

# A, Bの陣地数と多い方を出力する
a = count_box(map, A)
b = count_box(map, B)
puts "#{a} #{b}"
puts a > b ? "A" : "B"

試したこと

ローカルで実行してみたところ、1010マスでは問題なく動くが、10001000マスになると手番40回目あたりから動作に時間がかかってしまう。

補足情報（FW/ツールのバージョンなど）

使用言語：Ruby

Answer 1

どこに時間がかかっているかわからない。

とのことなので、まずはbenchmarkライブラリーを使って計測した方が良いかと思います。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "処理１" do
    # (計測したい処理その1)
  end
  r.report "処理２" do
    # (計測したい処理その2)
  end
end

↓

            user     system      total        real
処理１      1.217000   0.000000   1.217000 (  1.210070)
処理２      0.858000   0.000000   0.858000 (  0.856049)

参考：https://qiita.com/scivola/items/c5b2aeaf7d67a9ef310a