結果

問題 No.3 ビットすごろく
コンテスト
ユーザー seiichi
提出日時 2021-01-14 14:46:32
言語 Go
(1.23.4)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,150 bytes
コンパイル時間 11,751 ms
コンパイル使用メモリ 233,344 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 10:02:06
合計ジャッジ時間 13,010 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import (
	"fmt"
	"strconv"
)

func scan() (N int) {
	fmt.Scan(&N)
	return
}

func calcSteps(position int) (steps int) {
	s := strconv.FormatInt(int64(position), 2)
	for _, c := range s {
		if c == '1' {
			steps++
		}
	}
	return
}

type Item struct {
	currentPosition int
	numOfSteps      int
}

func main() {
	N := scan()
	// N := 4
	result := -1

	visited := map[int]bool{}
	var queue []Item
	queue = append(queue, Item{
		currentPosition: 1,
		numOfSteps:      1,
	})

	for len(queue) > 0 {
		item := queue[0]
		queue = queue[1:]

		if item.currentPosition == N {
			result = item.numOfSteps
			break
		} else if item.currentPosition < 1 || item.currentPosition > N {
			continue
		} else if visited[item.currentPosition] {
			continue
		}

		visited[item.currentPosition] = true
		steps := calcSteps(item.currentPosition)

		// go foward
		queue = append(queue, Item{
			currentPosition: item.currentPosition + steps,
			numOfSteps:      item.numOfSteps + 1,
		})
		// go backward
		queue = append(queue, Item{
			currentPosition: item.currentPosition - steps,
			numOfSteps:      item.numOfSteps + 1,
		})
	}

	fmt.Print(result)
}
0