groovyの勉強：ACM/ICPCの問題を解く

本日の題材は、2010年国内予選の問題Ｂ。きっと二番目に簡単な奴。
http://icpc2010.honiden.nii.ac.jp/domestic-contest/problems#section_B

問題Ａのときと同じように、eclipse開発だから、ファイルへの入出力へと変更した。
まあ、工夫したところはあまりなく、幅優先探索各セルのコストを求めつつ、番兵とかのテクニックを使ったことぐらいかなあ。幅優先探索だから、実際には、すでに計算済みのコストが上書きされることもないし、ゴールに着いたらループを抜けても良いんだけど、なんとなく、ガードをしておいた。

package acm.jp2010p

String.metaClass.toIntegers = { delegate.trim().split(/\s+/)*.toInteger() }
String.metaClass.toMapIntegers = { list -> [list, delegate.toIntegers()].transpose().collectEntries{it} }

lines = new File(args[0]).readLines()

new File(args[1]).withPrintWriter { out ->
	while( true ){
		size = lines.remove(0).toMapIntegers(['width', 'height'])
		if( size.width == 0 && size.height == 0 ){
			break
		}
		
		hwall = [[1]*size.width] // 横の壁
		vwall = [] // 縦の壁
		for( int y=0; y<size.height; y++ ){
			vwall << [1]+lines.remove(0).toIntegers()+[1]
			if( y < size.height-1 ){
				hwall << lines.remove(0).toIntegers()
			}
		}
		hwall << [1]*size.width
		costs = []
		size.height.times { costs << [Integer.MAX_VALUE]*size.width }
		
		queue = [[x:0, y:0, c:1]]
		costs[0][0] = 1
		while( queue.size() > 0 ){
			c = queue.remove(0)
			
			if( hwall[c.y][c.x] == 0 && costs[c.y-1][c.x] > c.c+1 ){
				queue << [x:c.x, y:c.y-1, c:c.c+1]
				costs[c.y-1][c.x] = c.c+1
			}
			if( hwall[c.y+1][c.x] == 0 && costs[c.y+1][c.x] > c.c+1 ){
				queue << [x:c.x, y:c.y+1, c:c.c+1]
				costs[c.y+1][c.x] = c.c+1
			}
			if( vwall[c.y][c.x] == 0 && costs[c.y][c.x-1] > c.c+1 ){
				queue << [x:c.x-1, y:c.y, c:c.c+1]
				costs[c.y][c.x-1] = c.c+1
			}
			if( vwall[c.y][c.x+1] == 0 && costs[c.y][c.x+1] > c.c+1 ){
				queue << [x:c.x+1, y:c.y, c:c.c+1]
				costs[c.y][c.x+1] = c.c+1
			}
		}
		
		if( costs[size.height-1][size.width-1] == Integer.MAX_VALUE ){
			out.println 0
		} else {
			out.println costs[size.height-1][size.width-1]
		}
	}
}

今回覚えたこと。

• *演算子：　まあ、あれば便利ぐらいか。
• Mapの値の取り方：　map.key = valueが出来るのは、手を抜くときにちょうど良い。

結局、今回も分からなかったこと。

• 多次元配列の楽な作り方