結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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
}
 
0