require 'csv'

# パネルクイズ全体
class Problem
  attr_accessor :lx, :rx, :ux, :dx, :n
  attr_accessor :boardList
end

# パネルクイズの「ボード」
class Board

  attr_accessor :w, :h # 幅、高さ
  attr_accessor :b, :e # ボードの現在状態、終了時の状態（char[]）
  attr_accessor :uf, :lf # 埋まっている行数（上部）、列数（左部）

  @@asc = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("")

  def initialize(w,h,b)
    @w = w; @h = h; @b = b.clone(); @uf = 0; @lf = 0
  end

  # 終了時の状態
  def endStatus()
    return @e if @e != nil
    buff = b.clone.sort()
    buff.delete("0")
    size = buff.size() - 1
    buff.delete("=")
    for i in 0..size
      buff[i,0] = "=" if buff[i] != @@asc[i]
    end
    buff << "0"
    @e = buff
  end

  # 左右上下の各方向について、０パネルが移動可能かどうかの判定
  def movable?()
    pos = b.index("0")
    l = (pos % w > lf)     && b[pos-1] != '=' # lf対策済み
    r = (pos % w != (w-1)) && b[pos+1] != '='
    u = (pos >= w*(1+uf))  && b[pos-w] != '=' # uf対策済み
    d = (b[pos+w] != nil)  && b[pos+w] != '='
    return [l, r, u, d]
  end

  # ０パネルをdirの方向に移動する
  def move(dir)
    pos    = b.index("0").to_i
    # p "pos:#{pos} dir:#{dir} w:#{w}"
    moveTo = { "l" => pos-1, "r" => pos+1, "u" => pos-w, "d" => pos+w }[dir]
    # tPos    = endStatus.index(b[pos])
    # tMoveTo = endStatus.index(b[moveTo])
    # p "pos=#{pos}, moveTo=#{moveTo}, " #tPos=#{tPos}, tMoveTo=#{tMoveTo}"
    swap(pos, moveTo)
    # p "score=#{score}"
    # p ["move::",diff(pos,tPos), diff(moveTo,tMoveTo), diff(moveTo,tPos), diff(pos,tMoveTo)]
    # score = score() # - diff(pos,tPos) - diff(moveTo,tMoveTo) + diff(moveTo,tPos) + diff(pos,tMoveTo)
    return self
  end

  # 新たに上部・左部が埋まったかどうかの判定
  def check ()
    # check_w
    w_filled = true
    for i in 0..(@h-1)
      pos = w * (i) + lf
      w_filled = false if ( b[pos] != "=" && b[pos] != @@asc[pos] )
    end
    #check_w
    h_filled = true
    for j in 0..(@w-1)
      pos = w * uf + j
      h_filled = false if ( b[pos] != "=" && b[pos] != @@asc[pos] )
    end
    return w_filled, h_filled
  end

  def swap(i,j)
    tmp = b[i]
    b[i] = b[j]
    b[j] = tmp
  end

  def print
    (0..(h-1)).any? {|i| p b[(i*w)..((i+1)*w-1)] }
  end

end

# ボードの局面
class State

  attr_accessor :key, :minPath #連想配列格納用のキー（ボード状態の文字列）、この局面に至る最小パス
  attr_accessor :board

  def initialize(board,minPath)
    @key       = board.b.join()
    @board     = board
    @minPath   = minPath
  end

  # dir方向に移動し、次の局面へ
  def move(dir)
    return State.new( Board.new(@board.w,@board.h,@board.b).move(dir), @minPath + dir )
  end

  # 終了判定
  def isEnd?
    return @board.b == @board.endStatus()
  end

  # どの程度埋まっているか？（高いほど、優先的に処理する）
  def lv?
    return board.lf + board.uf
  end

  def printState(message)
    l, r, u, d = board.movable?()
    print "------------------------------------------------\n"
    print "-- #{message}\n"
    print  "## path     ## [#{minPath}]\n"
    print  "## movable? ## l=#{l},r=#{r},u=#{u},d=#{d}\n"
    board.print()
  end
end

# 局面の重み付きキュー（lvが高いほど優先）
class StateQueue

  def initialize(n)
    @queues = Array.new
    for i in 0..n
      @queues[i] = Array.new
    end
  end

  def enqueue(state)
    lv = state.lv?
    @queues[lv] << state
  end

  def dequeue()
    for i in 1..@queues.size
      lv = @queues.size - i
      if @queues[lv]!=nil && @queues[lv].size > 0
        return @queues[lv].shift()
      end
    end
    p "nil"
    return nil
  end

  def size()
    size = 0
    for i in 0..@queues.size-1
      size = size + @queues[i].size() if @queues[i] != nil
    end
    return size
  end

  def to_s()
    a = Array.new
    for i in 0..@queues.size-1
      a[i] = @queues[i].size()
    end
    return "[#{a.join(',')}]"
  end

end

# 問題をCSVファイルから読む人
class ProblemReader
  def load(file)
    problem = Problem.new
    problem.boardList = Array.new
    i = 0
    CSV.open( file, 'r') do |row|
      case i
      when 0 then
        problem.lx, problem.rx, problem.ux, problem.dx = row[0].split(' ')
      when 1 then
        problem.n = row
      else
        board = Board.new(row[0].to_i, row[1].to_i, row[2].split(""))
        problem.boardList << board
      end
      i = i + 1
    end
    return problem
  end
end