結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー tshig
提出日時 2016-08-18 12:47:38
言語 Ruby
(3.4.1)
結果
AC  
実行時間 111 ms / 5,000 ms
コード長 1,046 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-11-07 19:17:03
合計ジャッジ時間 3,382 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class Calc0228
  def initialize(args)
    args = args.map { |l| l.chomp.split(/\s+/) }
    @as = args.map { |l| l.map(&:to_i) }
  end

  def calc
    as = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]]
    stack = [[as, []]]
    until stack.empty?
      as, used = stack.pop
      return true if goal?(as)
      x, y = find0(as)
      cands = [[x - 1, y], [x, y - 1], [x + 1, y], [x, y + 1]].select { |x2, y2|
        (0..3).include?(x2) && (0..3).include?(y2) && !used.include?(as[y2][x2])
      }
      cands.each do |x2, y2|
        as2 = dup(as)
        as2[y][x], as2[y2][x2] = as2[y2][x2], as2[y][x]
        stack.push([as2, used + [as2[y][x]]])
      end  
    end
    false
  end

  def goal?(as)
    @as.zip(as).all? { |r1, r2| r1 == r2 }
  end

  def find0(as)
    as.each_with_index do |r, y|
      r.each_with_index do |a, x|
        return x, y if a == 0
      end
    end
  end

  def dup(as)
    as.dup.map { |r| r.dup }
  end

  def run
    calc ? 'Yes' : 'No'
  end
end

puts Calc0228.new(STDIN.readlines).run if __FILE__ == $0
0