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

我使用了 CLRS 的标准 BFS 算法 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)
  }
}

Hackerrank：广度优先搜索：最短距离

Hackerrank: Breadth First Search: Shortest Reach

scala

breadth-first-search