結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2025-03-14 22:08:07 |
言語 | Go (1.23.4) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,070 bytes |
コンパイル時間 | 12,777 ms |
コンパイル使用メモリ | 235,180 KB |
実行使用メモリ | 15,420 KB |
最終ジャッジ日時 | 2025-03-14 22:08:27 |
合計ジャッジ時間 | 18,184 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 6 TLE * 1 -- * 25 |
ソースコード
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) type Station struct { position int canGoStationList []int } func main() { sc := bufio.NewScanner(os.Stdin) sc.Scan() firstInputs := strings.Fields(sc.Text()) stationNum, _ := strconv.Atoi(firstInputs[0]) minDis, _ := strconv.Atoi(firstInputs[1]) maxDis, _ := strconv.Atoi(firstInputs[2]) stationList := []Station{} sc.Scan() stringPosList := strings.Fields(sc.Text()) for _, s := range stringPosList { pos, _ := strconv.Atoi(s) station := Station{pos, []int{}} stationList = append(stationList, station) } // 各駅ごとに電車1本で到達可能な駅を探す for i := 0; i < stationNum; i++ { canGoStationList := []int{} for j := 0; j < stationNum; j++ { if i == j { continue } dis := stationList[i].position - stationList[j].position if dis < 0 { dis *= -1 } if dis >= minDis && dis <= maxDis { canGoStationList = append(canGoStationList, j) } stationList[i].canGoStationList = canGoStationList } } for _, station := range stationList { allCanGoStationList := searchCanGoStation([]int{}, stationList, station) if len(allCanGoStationList) == 0 { // 孤立のケース fmt.Println(1) } else { fmt.Println(len(allCanGoStationList)) } } } // 再帰を利用して到達可能な全ての駅を洗い出す func searchCanGoStation(canGoStationList []int, stationList []Station, station Station) []int { allCanGoStationList := canGoStationList for _, stationNum := range station.canGoStationList { if contains(canGoStationList, stationNum) { // 重複を避ける continue } else { canGoStationList = append(canGoStationList, stationNum) // 到達先の駅から行ける駅を探すため再帰 allCanGoStationList = searchCanGoStation(canGoStationList, stationList, stationList[stationNum]) } } return allCanGoStationList } // 重複チェック func contains(slice []int, value int) bool { for _, v := range slice { if v == value { return true } } return false }