結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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) }