読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

プログラミングコンテストの練習

D

この動画のおねえさんが好きすぎて困ってしまうのですが、、大好きすぎて日本科学未来館の展示にも思わず行ってしまったほど。
TAOCPが全巻揃っていた・・・あの声が館内に響きわたっていたなあ。
ちなみに、Knuthコンピュータ科学者がめったに語らないことにこの問題を乱数で近似的に解いたという話が載っていて、へえ。


さて、週末グラフの復習をした時にこの問題を再帰深さ優先探索で求めてみた。
さすがにN=6以上は時間がかかる。
漏れなく重複なく数え上げてくれるのだから、アルゴリズムってすごい。
おねえさんが手で4x4を解いたのは奇跡だと思うね。どうやったのかな?(おねえさんの声で)
今回、自分がグラフのことをよくわかっていなかったということが改めて分かった。
GCJの問題とか、よく解けてたよなあ。不思議だ。解けてなかったけどww
グラフが与えられた時に、ある頂点から深さ優先探索で全頂点を探索する、というのと
今回の問題のように、ある頂点から深さ優先探索である頂点までの経路を数え上げる、というのでは
問題のクラスが違っているのだなあ。多分、バックトラックなんだな。
今度このへん整理しよう。

N=5
class Graph
	def initialize(n)
		@n=n #num of vertex
		@e=Array.new(n){Array.new}
	end
	
	def add(v,w)
		@e[v]<<w
		@e[w]<<v
		self
	end

	def dfs_rec(s,g)
		@explored=Array.new(@n,false)
		@i=0
		@g=g
		def _dfs_rec(u)
			if u==@g
				@i+=1
				return
			end
			@explored[u]=true
			@e[u].each{|v|_dfs_rec(v) unless @explored[v]}
			@explored[u]=false
		end
		_dfs_rec(s)
		@i
	end
end

def p2v(i,j)
	N*i+j
end

g=Graph.new(N*N)
0.upto(N-1){|i|0.upto(N-2){|j|
	g.add(p2v(i,j),p2v(i,j+1))
}}
0.upto(N-1){|j|0.upto(N-2){|i|
	g.add(p2v(i,j),p2v(i+1,j))
}}

puts g.dfs_rec(0,N*N-1)