1

我正在尝试使用 scala解决codechef的倒水问题。问题陈述如下：

给定两个容器，其中一个可以容纳 1 升水，另一个可以容纳 b 升水，确定在其中一个容器中准确获得 c 升水所需的步骤数。

开始时，两个容器都是空的。以下操作计为“步数”：

emptying a vessel,
filling a vessel,
pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.

输入

一个整数t，1<=t<=100，表示测试用例的个数，后面跟着t组输入数据，每组由三个正整数a（第一个容器能装的升数），b（个数第二个容器可以容纳的升数）和 c（一个容器应包含的最终水升量），不大于 40000，在单独的行中给出。

输出

对于每组输入数据，输出获得 c 升所需的最小步数，如果不可能，则输出 -1。

示例 示例输入：

2 5 2 3 2 3 4

样本输出：

2 -1

我将这个问题作为图论问题来处理。给定容器的初始配置为(0, 0)，我通过应用操作获得容器的下一个状态：

FillA, FillB, PourAtoB, PourBtoA, EmptyA,EmptyB递归直到达到目标。

我的代码如下：

import scala.collection.mutable.Queue

def pour(initA:Int, initB:Int, targetCapacity:Int) {
    var pourCombinations = new scala.collection.mutable.HashMap[(Int, Int),Int]
    val capacityA = initA
    val capacityB = initB

    val processingQueue = new Queue[(Int, Int, Int, Int)]

    def FillA(a:Int, b:Int) = {
      (capacityA, b)                    
    }
    def FillB(b:Int, a:Int) = {
      (a, capacityB)
    }   
    def PourAtoB(a:Int, b:Int): (Int, Int) = {
      if((a == 0) || (b == capacityB)) (a, b) 
      else PourAtoB(a - 1, b + 1) 
    }
    def PourBtoA(b:Int, a:Int): (Int, Int) = { 
      if((b == 0) || (a == capacityA)) (a, b) 
      else PourBtoA(b - 1, a + 1)
    }
    def EmptyA(a:Int, b:Int) = {
      (0, b)
    }
    def EmptyB(a:Int, b:Int) = {
      (a, 0)
    }

    processingQueue.enqueue((0, 0, targetCapacity, 0))
    pourCombinations((0, 0)) = 0


    def pourwater(a:Int, b:Int, c:Int, numSteps:Int): Int = {
        println(a + ":" + b + ":" + c + ":" + numSteps)

        if((a == c) || (b == c)) {return numSteps}

        if(processingQueue.isEmpty && (pourCombinations((a,b)) == 1)) {return -1}

        //Put all the vals in a List of tuples
        val pStateList = scala.List(FillA(a, b), FillB(a, b), PourAtoB(a, b), PourBtoA(b, a), EmptyA(a, b), EmptyB(a, b))       

        pStateList.foreach{e =>
          {
            if(!pourCombinations.contains(e)) {
              pourCombinations(e) = 0
              processingQueue.enqueue((e._1, e._2, c, numSteps + 1))
            }
          }
        }   
        pourCombinations((a, b)) = 1
        val processingTuple = processingQueue.dequeue()
        pourwater(processingTuple._1, processingTuple._2, processingTuple._3, processingTuple._4)

     }
     val intialvalue = processingQueue.dequeue()
     pourwater(intialvalue._1, intialvalue._2, intialvalue._3, intialvalue._4)
}

这有几个问题，首先我不确定我的递归步骤设置是否正确。另外，可能是我没有使用正确的 Scala 约定来解决这个问题。另外，我希望 pour 函数在numSteps完成执行后返回。目前它没有这样做。

如果有人可以通过我的代码并指出我的方法的错误，那就太好了。

谢谢

4

0 回答 0