結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2018-09-30 01:09:29 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,514 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-10-12 08:56:54 |
合計ジャッジ時間 | 2,787 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 WA * 22 |
ソースコード
# -*- coding: utf-8 -*-# !/usr/bin/env python# vim: set fileencoding=utf-8 :"""## Author: Noname# URL: https://github.com/pettan0818# License: MIT License# Created: 金 9/28 23:04:27 2018# Usage#"""from collections import dequedef get():""""""return int(input())def get_each_cell_num(length):""">>> get_each_cell_num(5)[1, 1, 2, 1, 2]"""def maker(num):return sum([int(i) for i in list(bin(num)[2:])])return [maker(i) for i in range(1, length+1)]def bfs(res, goal, route):QUE = deque([])goal = goal - 1 # 配列と問題文のIndexは1差がある。res[0] = 1QUE.append(0)while QUE: # Listが空だとFalse# print(res)pos = QUE.popleft()# print(pos)if pos == goal: # ゴールに着いたら探索不要return resfor i in [route[pos], -route[pos]]:next_pos = pos + iif next_pos >= len(res):continueif next_pos >= 0 and res[next_pos] == -1:QUE.append(next_pos)# print("next_pos: ", next_pos)# print("res: ", res)# print("QUE: ", QUE)res[next_pos] = res[pos]return resdef solve(length):""">>> solve(5)"""res = [-1] * lengthroute = get_each_cell_num(length)shortest_path = bfs(res, length, route)print(shortest_path[-1])if __name__ == '__main__':solve(get())