# TODO: bez_zvedu_skrz_zdi/vstup6.in

require 'set'

class Pozice
	def initialize(x,y)
		@x = x
		@y = y
	end

	attr_accessor :x, :y

	def eql?(other)
		x == other.x && y == other.y
	end

	def ==(other)
		eql? other
	end
	
	def +(other)
		Pozice.new(x + other.x, y + other.y)
	end

	def hash
		[ x, y ].hash
	end

	def to_s
		"[#{x};#{y}]"
	end
end

class Spion
	def initialize(x,y,sekvence)
		@x = x
		@y = y
		@sekvence = sekvence
	end

	attr_accessor :x, :y, :sekvence
end

class StavSpiona
	def initialize(spion)
		@i = 0
		@delta = Pozice.new(0,0)
		@spion = spion
	end

	attr_accessor :i, :delta, :spion

	def dup
		s = StavSpiona.new(spion)
		s.i = i
		s.delta = delta.dup
		s
	end

	def tick
		s = dup
		s.tick!
		s
	end

	def tick!
		case @spion.sekvence[@i]
			when ?<
				@delta.x -= 1
			when ?>
				@delta.x += 1
			when ?v
				@delta.y += 1
			when ?^
				@delta.y -= 1
		end
		@i = (@i + 1) % @spion.sekvence.length	
	end

	def x
		@spion.x + @delta.x
	end

	def y
		@spion.y + @delta.y
	end
	# TODO: neprochazi bludistem
	
	def eql?(other)
		@i == other.i
	end

	def hash
		@i
	end

	def ==(other) eql? other end

	def to_s
		#"@[#{x};#{y}]"
		"@#{i}"
	end
end

class StavBludiste
	def initialize()
		@poziceSpionu = []
		@pruchodu = 0
	end

	def StavBludiste.pro_bludiste(bludiste)
		StavBludiste.new.pro_bludiste(bludiste)
	end

	def pro_bludiste(bludiste)
		@bludiste = bludiste
		@bila_pani = bludiste.bila_pani

		for i in bludiste.spioni
			@poziceSpionu << StavSpiona.new(i)
		end

		self
	end

	def spion_na(x,y)
		for i in @poziceSpionu
			return true if i.x == x && i.y == y
		end
		false
	end

	def bila_pani_na(x,y)
		@bila_pani.x == x && @bila_pani.y == y
	end

	def zapomen_pruchody
		v=dup
		v.pruchodu = 0
		v
	end

	attr_accessor :pruchodu
	def hash
		h = @bila_pani.hash
		for i in @poziceSpionu
			h += i.hash
		end
		h += @pruchodu.hash
		h
	end

	def eql?(other)
		return false if !@pruchodu.eql? other.pruchodu
		return false if !@bila_pani.eql? other.bila_pani

		for i in @poziceSpionu.each_index
			return false if !@poziceSpionu[i].eql? other.poziceSpionu[i]
		end
	
		true
	end

	def hash
		h=[ @pruchodu, @bila_pani, @poziceSpionu ].hash
		h
	end

	def tick!
		for sp in @poziceSpionu
			sp.tick!
		end
	end

	# TODO: predat taky moznosti...
	def naslednici(zvedove, prochazeni)
		result = []
		for delta in [ Pozice.new(-1,0), Pozice.new(1,0), Pozice.new(0,1), Pozice.new(0,-1) ]
			bp = @bila_pani + delta
			s = StavBludiste.new
			s.bludiste = bludiste
			s.bila_pani = bp
			s.pruchodu = pruchodu
			s.predchozi = self
			s.poziceSpionu = []
			for i in poziceSpionu
				s.poziceSpionu << i.dup
			end
			s.tick!
			next if !s.ok?(zvedove, prochazeni)

			result << s
		end
		result
	end

	def ok?(zvedove, prochazeni)
		return false if !(bila_pani.x >= 0 && bila_pani.x < bludiste.width &&
			bila_pani.y >= 0 && bila_pani.y < bludiste.height)

		if zvedove
			return false if spion_na(bila_pani.x, bila_pani.y)

			if !predchozi.nil?
				#puts "LBP #{predchozi.bila_pani} NBP #{bila_pani}"
				#puts "podmA" if spion_na(predchozi.bila_pani.x, predchozi.bila_pani.y)
				#puts "podmB" if predchozi.spion_na(bila_pani.x, bila_pani.y)
				#return false if predchozi.spion_na(bila_pani.x, bila_pani.y)
				return false if spion_na(predchozi.bila_pani.x, predchozi.bila_pani.y) && predchozi.spion_na(bila_pani.x, bila_pani.y)
			end
		end
		
		return false if !prochazeni && bludiste.zed_na(bila_pani.x, bila_pani.y)

		true
	end

	def to_s
		ps = poziceSpionu.map { |x| x.to_s }.join ","

		"BP:#{bila_pani}, PS:#{ps}, P=#{pruchodu}"
	end

	attr_accessor :bila_pani, :poziceSpionu, :bludiste, :predchozi
end

class Bludiste
	def initialize
		@width = 8
		@height = 8
		@spioni = []
	end

	def Bludiste.load(file)
		Bludiste.new.load file
	end

	attr_accessor :width, :height, :spioni, :bila_pani, :televize, :zdi

	def pridej_bilou_pani(i, j)
		@bila_pani = Pozice.new i,j
	end

	def pridej_televizi(i, j)
		@televize = Pozice.new i,j
	end

	def pridej_spiona(i, j, sekvence)
		@spioni << Spion.new(i,j,sekvence)
	end

	# TODO: vystridani se se zvedem
	def search(zvedove, prochazeni, delka)
		nejlepsi_pruchody = {}

		queue = []
		projite = Set.new
		base = StavBludiste.pro_bludiste(self)
		base.pruchodu = 0
		queue << base
		vysledek = nil

		min_pruchodu = nil

		while !queue.empty?	
			stav = queue.shift
			#p stav
			#p stav.predchozi

			if stav.bila_pani == @televize
				if delka == :slapnuti
					vysledek = stav
					break
				else
					if min_pruchodu.nil? || min_pruchodu > stav.pruchodu
						min_pruchodu = stav.pruchodu
						vysledek = stav	
					end
				end
			end

			for n in stav.naslednici(zvedove, prochazeni)
				if zed_na(n.bila_pani.x,n.bila_pani.y)
					n.pruchodu += 1
				end
				next if !min_pruchodu.nil? && n.pruchodu > min_pruchodu
				if delka == :pruchody
					fgt = n.zapomen_pruchody
					if (!nejlepsi_pruchody.has_key? fgt) || nejlepsi_pruchody[fgt].pruchodu > stav.pruchodu
						nejlepsi_pruchody[fgt]=n
					else
						#puts "Cull: #{n} VS #{nejlepsi_pruchody[fgt]}"
						next
					end
				end
				queue << n if !projite.include?(n)
				projite << n
			end

			#puts "Q:#{queue.join ','}"
		end

		return nil if vysledek.nil?

		stav = vysledek
		sst = stav

		vysledek = []
		while !stav.nil?
			vysledek << stav
			stav = stav.predchozi
		end

		vysledek.reverse!
		#p vysledek
		vysledek
	end

	def read_line(n, line)
		i = 0
		j = 0
		while j < line.length
			case line[j]
				when ?&
					@zdi[n][i] = false
					pridej_bilou_pani i,n
				when ?X
					@zdi[n][i] = true
				when ?.
					@zdi[n][i] = false
				when ?#
					@zdi[n][i] = false
					pridej_televizi i,n
				when ?@
					@zdi[n][i] = false
					sekvence = ""
					j += 1
					while line[j] =~ /[v^<>]/
						sekvence << line[j]
						j += 1
					end
					j -= 1
					#puts sekvence
					pridej_spiona i,n,sekvence
			end
			i += 1
			j += 1
		end
	end

	def load(file)
		File.open file do |f|
			@width, @height = f.readline.split(" ").map {|x| x.to_i}
			@zdi = []

			for i in 0...@height
				@zdi << [nil] * @width
			end

			i = 0
			while (line = f.gets)
				read_line i, line
				i += 1
			end
		end
		self
	end

	def empty!
		@bila_pani = nil
		@televize = nil
		
		@zdi = []

		for i in 0...@height
			@zdi << [false] * @width
		end
	end

	def bila_pani_na(x, y,stav = nil)
		return @bila_pani.x == x && @bila_pani.y == y if stav.nil?
		stav.bila_pani_na(x,y)
	end

	def televize_na(x, y)
		return false if !@televize
		@televize.x == x && @televize.y == y
	end

	def spion_na(x, y, stav=nil)
		stav = StavBludiste.pro_bludiste(self) if stav.nil?
		stav.spion_na x,y
	end

	def zed_na(x, y)
		@zdi[y][x]
	end

	def symbol_at i,j,stav
		return "&" if bila_pani_na i,j,stav
		return "@" if spion_na i,j,stav
		return "#" if televize_na i,j
		return "X" if zed_na i,j
		return "."
	end

	def render(stav=nil)
		stav = StavBludiste.pro_bludiste(self) if stav.nil?
		result = ""
		for i in 0...@height
			for j in 0...@width
				result << symbol_at(j, i, stav)
			end
			result << "\n"
		end
		result
	end
end