結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー tshigtshig
提出日時 2016-08-18 12:47:38
言語 Ruby
(3.3.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 108 ms
12,288 KB
testcase_01 AC 88 ms
12,032 KB
testcase_02 AC 103 ms
12,160 KB
testcase_03 AC 106 ms
12,288 KB
testcase_04 AC 100 ms
12,288 KB
testcase_05 AC 85 ms
12,160 KB
testcase_06 AC 108 ms
12,288 KB
testcase_07 AC 92 ms
12,160 KB
testcase_08 AC 109 ms
12,416 KB
testcase_09 AC 93 ms
12,032 KB
testcase_10 AC 106 ms
12,416 KB
testcase_11 AC 96 ms
12,288 KB
testcase_12 AC 110 ms
12,416 KB
testcase_13 AC 106 ms
12,288 KB
testcase_14 AC 108 ms
12,416 KB
testcase_15 AC 107 ms
12,160 KB
testcase_16 AC 108 ms
12,288 KB
testcase_17 AC 111 ms
12,288 KB
testcase_18 AC 107 ms
12,288 KB
testcase_19 AC 107 ms
12,288 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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