我正在尝试使用 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
完成执行后返回。目前它没有这样做。
如果有人可以通过我的代码并指出我的方法的错误,那就太好了。
谢谢