用Scala 解决Gnome Tetravex

Gnome Teltravex 是一个ACM练习题目，完整的描述在这里http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=8

我主要是为了学习scala语言，所以实现可能有问题；我只是简单的测试一下，因为无法提交，所以无法完全确定这个实现是否正确。但这个不是重点。重点是scala。

代码：

 

 

/**
 *
 */

/**
 * @author Blues
 *
 */
class Square(t: Int, r: Int, b: Int, l: Int) {
  val top = t;
  val right = r;
  val bottom = b;
  val left = l;

  override def toString() = "Square [top: " + top + ", right: " + right + ", bottom: " + bottom + ", left: " + left + "]";
  
  override def equals(that: Any):Boolean = that match {
    case that: Square =>  (top == that.top && right == that.right && bottom == that.bottom && left == that.left)
    case _ => false
  }
}

object App {
  def main(args: Array[String]) {
    readAndProcess(readLine, 0);
  }

  def readAndProcess(line: String, counter: Int) {
    val n = line.toInt;
    if (n == 0) {
      return ;
    } else {
      //for 也是表达式，可以使用yield计算
      val squares = for (i <- 0 until n * n) yield {
        val squareLine = readLine();
        val nums = squareLine.split(" ");
        if (nums.length == 4) {
          new Square(nums(0).toInt, nums(1).toInt, nums(2).toInt, nums(3).toInt)
        } else {
          throw new Exception("wrong input");
        }
      }
      val succeeded = process(n, squares.toArray);
      if (succeeded) {
        println("Game " + counter + ": Possible")
      } else {
        println("Game " + counter + ": Impossible")
      }
      //使用递归避免使用while；while没有计算结果，在函数式语言里不被提倡
      readAndProcess(readLine, (counter + 1));
    }
  }

  def process(n: Int, squares: Array[Square]): Boolean = {
    //在函数里定义函数，这个算闭包么？
    def pickSquare(proccededSquares: List[Square]): List[Square] = {
    	squares.filterNot(proccededSquares.contains(_)).toList;
    }

    def dfs(index: Int, proccededSquares: List[Square]): Boolean = {
      //var定义可变变量，不提倡
      var done = false;
      for (pickedSquare <- pickSquare(proccededSquares)
          if !done) {
        val currentRow = index / n;
        val currentCol = index % n;
        //if 也可以计算结果，如此就可以将matched定义为val，不可变类型；
        val matchTop = if (currentRow > 0) {
          val topIndex = (currentRow - 1) * n + currentCol;
          val topSquare = proccededSquares(topIndex);
          topSquare.bottom == pickedSquare.top
        } else {
          true;
        }

        val matchLeft = if (currentCol > 0) {
          val leftIndex = index - 1;
          val leftSquare = proccededSquares(leftIndex);
          leftSquare.right == pickedSquare.left;
        } else {
          true;
        }

        if (matchTop && matchLeft) {
          //list :: 是右操作符，由右边的值调用，并把左边的值作为参数传入
          val addCurrent = (pickedSquare :: (proccededSquares.reverse)).reverse
          println(addCurrent)
          done = dfs(index + 1, addCurrent)
        }
      }
      done;
    }

    dfs(0, Nil);
  }

}

 重点都在注释里面。

 

刚开始学习scala，发现它还是很有趣。