結果

問題 No.1576 織姫と彦星
ユーザー lam6er
提出日時 2025-03-31 17:46:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 522 ms / 2,000 ms
コード長 1,220 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 76,776 KB
最終ジャッジ日時 2025-03-31 17:47:46
合計ジャッジ時間 10,094 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

n = int(input())
start, end = map(int, input().split())
stones = list(map(int, input().split()))

# Create a list of all nodes including start, stones, and end
nodes = [start] + stones + [end]
total_nodes = len(nodes)
end_idx = total_nodes - 1  # Index of the end node

distance = [-1] * total_nodes
distance[0] = 0  # Start node is at index 0

q = deque([0])

found = False
while q:
    current = q.popleft()
    
    # Check if current node is the end node
    if current == end_idx:
        found = True
        break
    
    current_val = nodes[current]
    for other_idx in range(total_nodes):
        if other_idx == current:
            continue
        other_val = nodes[other_idx]
        # Calculate Hamming distance
        xor = current_val ^ other_val
        ham = bin(xor).count('1')
        if ham <= 1 and distance[other_idx] == -1:
            distance[other_idx] = distance[current] + 1
            q.append(other_idx)
            if other_idx == end_idx:
                found = True
                # Early exit if end is found
                q = deque()
                break

if distance[end_idx] == -1:
    print(-1)
else:
    print(max(0, distance[end_idx] - 1))
0