[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[jfriends-ml 13318] グループ 3 の Scala ソースコード

松永です。合宿お疲れ様でした。

世話人の高橋(智)さんの練り上げられた計画のおかげで、気持ちよく学習、観光
できました。ありがとうございました。

グループ3の発表で披露したScalaのソースコードとテストデータを添付します。

-- 
松永直人(MATSUNAGA Naoto)
naoto@xxxxxx







object MinCost {
  def main(args: Array[String]) {
	val rowSize = args(0).toInt
	val colSize = args(1).toInt
	
	// 最小コストのルート、最小コストを保存
	var minCostRoute: List[(Int, Int)] = Nil
	var minCost = 0

	// コストマップ作成
	val costMap: Map[(Int, Int), Int] = {
	  val costs = for (i <- 0 until rowSize*colSize) yield args(i + 2).toInt
	  val cells = for {
		row <- 0 until rowSize
		col <- 0 until colSize
	  } yield (row, col)
	  Map() ++ (cells.toList zip costs.toList);
	}

	// ルートのコストを計算
	def cost(xs: List[(Int, Int)]): Int = (0 /: xs) (_ +costMap(_))

	// セルがマップ内か判定
	def inMap(cell: (Int,Int)): Boolean = {
	  0 <= cell._1 && cell._1 < rowSize && 0 <= cell._2 && cell._2 < colSize
	}

	// 次のセル候補をルートに追加
	def pushNextCell(route: List[(Int, Int)], nextCell: (Int, Int)) {
	  // セル候補がマップ内部かチェック
	  if (!inMap(nextCell)) return
	  // 既に通ったセルかチェック
	  if (route.contains(nextCell)) return
	  // 現時点での最小コストを既に超過していないかチェック
	  if (minCostRoute != Nil && cost(nextCell :: route) >= minCost) return
	  // ゴールに到達しているかチェック、していれば登録
	  if (nextCell == (rowSize - 1, colSize - 1)) {
		minCostRoute = nextCell :: route
		minCost = cost(minCostRoute)
		return
	  }

	  // 次のセル候補を選択、ルートに追加
	  pushNextCell(nextCell :: route, (nextCell._1, nextCell._2 + 1))
	  pushNextCell(nextCell :: route, (nextCell._1, nextCell._2 - 1))
	  pushNextCell(nextCell :: route, (nextCell._1 + 1, nextCell._2))
	  pushNextCell(nextCell :: route, (nextCell._1 - 1, nextCell._2))
	}

	// 処理開始
	pushNextCell(Nil, (0, 0))

	// 結果出力
	println("minCost: " + minCost)
	println(minCostRoute.reverse)
  }
}

【実行手順】

scalac MinCost.scalaでコンパイル後、下記の要領で呼び出し。

scala MinCost 行数 列数 1行目の各列のコスト 2行目の各列のコスト列 ...

　　結果は(行番号, 列番号)のタプルのリストの形式で出力される。

【例】

scala MinCost 5 5  1 2 1 1 2  1 1 1 2 1  2 2 1 1 2  1 2 1 2 2  1 1 1 1 1 

　　これは、5行5列の下記のコストを持つセルからなる下記の領域を意味する。

　　1 2 1 1 2 
　　1 1 1 2 1  
　　2 2 1 1 2  
　　1 2 1 2 2 
　　1 1 1 1 1