Hackerrank：廣度優先搜索：最短河段

Question

問題陳述：https://www.hackerrank.com/challenges/bfsshortreach

我的解決方案：

import scala.collection.mutable._ 
import scala.io.StdIn._ 

object Solution { 

    def BFS(g: Array[ListBuffer[Int]], s: Int): Array[Int] = { 
    val n = g.length 
    val color = new Array[String](n) 
    val distance = new Array[Int](n) 
    for (i <- 1 until n) { 
     if (i != s) { 
     color(i) = "White" 
     distance(i) = -1 
     } 
    } 

    color(s) = "Gray" 
    distance(s) = 0 
    val Q = Queue[Int]() 
    Q.enqueue(s) 
    while (Q.nonEmpty) { 
     val u = Q.dequeue() 
     g(u).foreach(v => { 
     if (color(v) == "White") { 
      color(v) = "Gray" 
      distance(v) = distance(u) + 6 
      Q.enqueue(v) 
     } 
     }) 
     color(u) = "Black" 
    } 
    distance 
    } 

    def main(args: Array[String]): Unit = { 
    val q = readLine().replaceAll("""(?m)\s+$""", "").toInt 
    val sb = StringBuilder.newBuilder 
    for (_ <- 1 to q) { 
     var s = readLine().replaceAll("""(?m)\s+$""", "").split(" ") 
     val n = s(0).toInt 
     val m = s(1).toInt 
     val g = new Array[ListBuffer[Int]](n + 1) 

     for (i <- 1 to n) { 
     g(i) = ListBuffer[Int]() 
     } 

     for (_ <- 1 to m) { 
     s = readLine().replaceAll("""(?m)\s+$""", "").split(" ") 
     val u = s(0).toInt 
     val v = s(1).toInt 
     g(u).append(v) 
     } 
     val source = readLine().replaceAll("""(?m)\s+$""", "").toInt 
     val distance = BFS(g, source) 
     for (i <- 1 to n) { 
     if (i != source) { 
      sb.append(distance(i) + " ") 
     } 
     } 
     sb.append("\n") 
    } 
    println(sb) 
    } 
} 

我使用的標準BFS算法從CLRS Source 除了基礎測試的情況下，每一個其他測試案件失敗。無法確定此實施的問題。任何幫助，將不勝感激！

注： 「的replaceAll（」 「」（M）\ S + $ 「」 「 」「？）」 是從原始輸入刪除尾部空格

Answer 1

我錯過一個關鍵細節：邊緣是雙向和輸入不提供這兩種情況。 例如：對於邊（u，v）和（v，u），輸入只包含（u，v）。

最終解決方案：

import scala.collection.mutable._ 
import scala.io.StdIn._ 

object Solution { 
    def BFS(g: Array[Set[Int]], s: Int): Array[Int] = { 
    val n = g.length 
    val color = new Array[String](n) 
    val distance = new Array[Int](n) 
    for (i <- 1 until n) { 
     if (i != s) { 
     color(i) = "White" 
     distance(i) = -1 
     } 
    } 

    color(s) = "Gray" 
    distance(s) = 0 
    val Q = Queue[Int]() 
    Q.enqueue(s) 
    while (Q.nonEmpty) { 
     val u = Q.dequeue() 
     g(u).foreach(v => { 
     if (color(v) == "White") { 
      color(v) = "Gray" 
      distance(v) = distance(u) + 6 
      Q.enqueue(v) 
     } 
     }) 
     color(u) = "Black" 
    } 
    distance 
    } 

    def main(args: Array[String]): Unit = { 
    val q = readLine().replaceAll("""(?m)\s+$""", "").toInt 
    val sb = StringBuilder.newBuilder 
    for (_ <- 1 to q) { 
     var s = readLine().replaceAll("""(?m)\s+$""", "").split(" ") 
     val n = s(0).toInt 
     val m = s(1).toInt 
     val g = new Array[Set[Int]](n + 1) 

     for (i <- 1 to n) { 
     g(i) = Set[Int]() 
     } 

     for (_ <- 1 to m) { 
     s = readLine().replaceAll("""(?m)\s+$""", "").split(" ") 
     val u = s(0).toInt 
     val v = s(1).toInt 
     g(u).add(v) 
     g(v).add(u)  
     } 
     val source = readLine().replaceAll("""(?m)\s+$""", "").toInt 
     val distance = BFS(g, source) 
     for (i <- 1 to n) { 
     if (i != source) { 
      sb.append(distance(i) + " ") 
     } 
     } 
     sb.append("\n") 
    } 
    println(sb) 
    } 
}