[PYTHON] Sie wandeln spiralförmig in einer Welt, in der sich die Wände des Kreuzes erheben (Simulation)

Über Eingabe und Ausgabe

Alle folgenden Antworten verwenden die Standardeingabe / -ausgabe, daher benötige ich ein Bewertungswerkzeug. https://github.com/cielavenir/procon/blob/498c9856ea73bf871c15575e2d21bae7263d1167/hena/tyama_hena_validator.rb Mit hena_validator.rb hena28.py 28 ausführen.

Sie können jedoch zusätzliche Fragen einwerfen, ohne das Bewertungswerkzeug zu verwenden.

Richtige Methode (Python / Ruby / C ++)

Es gibt eine richtige Methode als Algorithmus, um das Labyrinth zu lösen. Wenn es nur eine Wand gibt (topologisch), müssen Sie gehen, ohne Ihre rechte Hand loszulassen, um das Ziel zu erreichen. Dies entspricht dem Versuch, aus Fahrtrichtung immer nach rechts abzubiegen.

CheckiO hat ein Problem mit Lantern Festival. Die Frage nach der Beantwortung der Anzahl der Zellen, die derzeit beim Spülen der Laterne leuchten. Dies kann auch mit der richtigen Methode gelöst werden, also habe ich diesmal die Maze-Klasse verwendet. Daher ist diesmal die Hauptsprache Python. Die Ruby-Version ist ein Port davon.

Die C ++ - Version des CodeIQ-Algorithmus dieser Woche Meet in the labyrinth? .

hena28.py

#!/usr/bin/env python
#http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
#http://nabetani.sakura.ne.jp/hena/ord28spirwa/

D=( #Right,Up,Left,Down
	(0,1),
	(-1,0),
	(0,-1),
	(1,0),
)
dir=['E','N','W','S']

class Maze:
	def __init__(self,x,y,d,v):
		self.x=x
		self.y=y
		self.d=d
		self.v=v
		self.v[self.y][self.x]='*'
		self.route=[]
		self.route.append((self.x,self.y))
	def move(self):
		d_orig=(self.d+3)%4
		for i in range(4):
			self.d=(d_orig+i)%4
			if self.v[self.y+D[self.d][0]][self.x+D[self.d][1]]=='.': break
		self.y=self.y+D[self.d][0]
		self.x=self.x+D[self.d][1]
		self.v[self.y][self.x]='*'
		self.route.append((self.x,self.y))

if __name__=='__main__':
	import sys
	if sys.version_info[0]>=3: raw_input=input
	Z=100
	try:
		while True:
			line=raw_input().rstrip().split(':')
			n,e,s,w=[int(e) for e in line[0].split(',')]
			days=int(line[1])
			m=[['.']*(Z*2) for i in range(Z*2)]
			m[Z][Z]='*'
			for i in range(n): m[Z-i-1][Z]='*'
			for i in range(e): m[Z][Z+i+1]='*'
			for i in range(s): m[Z+i+1][Z]='*'
			for i in range(w): m[Z][Z-i-1]='*'
			maze=Maze(Z+1,Z-1,0,m)
			for i in range(days+1):maze.move()
			print(dir[maze.d])
			sys.stdout.flush()
	except EOFError:
		pass

hena28.rb

#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
#http://nabetani.sakura.ne.jp/hena/ord28spirwa/

D=[ #Right,Up,Left,Down
	[0,1],
	[-1,0],
	[0,-1],
	[1,0],
]
dir=['E','N','W','S']

class Maze
	attr_reader :d
	def initialize(x,y,d,v)
		@x=x
		@y=y
		@d=d
		@v=v
		@v[@y][@x]='*'
		@route=[]
		@route<<[@x,@y]
	end
	def move
		d_orig=(@d+3)%4
		4.times{|i|
			@d=(d_orig+i)%4
			break if @v[@y+D[@d][0]][@x+D[@d][1]]=='.'
		}
		@y=@y+D[@d][0]
		@x=@x+D[@d][1]
		@v[@y][@x]='*'
		@route<<[@x,@y]
	end
end

if __FILE__==$0
	Z=100
	while gets
		line=$_.chomp.split(':')
		n,e,s,w=line[0].split(',').map(&:to_i)
		days=line[1].to_i
		m=(Z*2).times.map{['.']*(Z*2)}
		m[Z][Z]='*'
		n.times{|i|m[Z-i-1][Z]='*'}
		e.times{|i|m[Z][Z+i+1]='*'}
		s.times{|i|m[Z+i+1][Z]='*'}
		w.times{|i|m[Z][Z-i-1]='*'}
		maze=Maze.new(Z+1,Z-1,0,m)
		(days+1).times{maze.move}
		puts dir[maze.d]
		STDOUT.flush
	end
end

hena28.cpp

// http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
// http://nabetani.sakura.ne.jp/hena/ord28spirwa/

#include <cstdio>
#include <string>
#include <vector>
using namespace std;
const int D[4][2]={ //Right,Up,Left,Down
	{0,1},
	{-1,0},
	{0,-1},
	{1,0},
};

class Maze{
	vector<string> &v;
	int x,y,d;
public:
	Maze(int _x,int _y,int _d,vector<string>&_v)
		: x(_x),y(_y),d(_d),v(_v){
			v[y][x]='*';
	}
	void move(){
		int d_orig=(d+3)%4,i=0;
		for(;i<4;i++){
			d=(d_orig+i)%4;
			if(v[y+D[d][0]][x+D[d][1]]=='.')break;
		}
		y=y+D[d][0];
		x=x+D[d][1];
		v[y][x]='*';
	}
	int dir(){return d;}
};

int main(){
	const string dir="ENWS";
	const int Z=100;
	int n,e,s,w;
	long long days;
	for(;scanf("%d,%d,%d,%d:%lld",&n,&e,&s,&w,&days);){
		vector<string> m(Z*2);
		for(int i=0;i<Z*2;i++)m[i]=string(Z*2,'.');
		m[Z][Z]='*';
		for(int i=0;i<n;i++)m[Z-i-1][Z]='*';
		for(int i=0;i<e;i++)m[Z][Z+i+1]='*';
		for(int i=0;i<s;i++)m[Z+i+1][Z]='*';
		for(int i=0;i<w;i++)m[Z][Z-i-1]='*';
		Maze maze(Z+1,Z-1,0,m);
		for(int i=0;i<=days;i++)maze.move();
		printf("%c\n",dir[maze.dir()]);
		fflush(stdout);
	}
}

Eine weitere Lösung für die Simulation (Ruby)

Wenn Sie ein Labyrinth lösen, denken Sie normalerweise an die Richtung, in die Sie blicken. Diesmal ** erscheinen jedoch keine Dellen in der Abbildung **, sodass das Problem gelöst werden kann, ohne die Richtung aufzuzeichnen, in die es zeigt. Eine Strategie, um ein bisschen zu stehen und die Richtung der Wand zu halten. Es gibt Regelmäßigkeit in dieser "Richtung". Es ist leicht zu verstehen, ob Sie case-when verwenden.

hena28_another.rb

#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
#http://nabetani.sakura.ne.jp/hena/ord28spirwa/

D=[ #Right,Up,Left,Down
	[0,1],
	[-1,0],
	[0,-1],
	[1,0],
]
dir=['E','N','W','S']

class Maze
	def initialize(x,y,v)
		@x=x
		@y=y
		@v=v
		@v[@y][@x]='*'
	end
	def move
		walls=D.each_with_index.map{|e,i|@v[@y+e[0]][@x+e[1]]=='*' ? 1<<i : 0}.reduce(:+)
		d=case walls
			when 8,8+4,8+6
				0
			when 1,1+8,1+12
				1
			when 2,2+1,2+9
				2
			when 4,4+2,4+3
				3
			else
				raise
		end
		@y=@y+D[d][0]
		@x=@x+D[d][1]
		@v[@y][@x]='*'
		d
	end
end

if __FILE__==$0
	Z=100
	while gets
		line=$_.chomp.split(':')
		n,e,s,w=line[0].split(',').map(&:to_i)
		days=line[1].to_i
		m=(Z*2).times.map{['.']*(Z*2)}
		m[Z][Z]='*'
		n.times{|i|m[Z-i-1][Z]='*'}
		e.times{|i|m[Z][Z+i+1]='*'}
		s.times{|i|m[Z+i+1][Z]='*'}
		w.times{|i|m[Z][Z-i-1]='*'}
		maze=Maze.new(Z+1,Z-1,m)
		days.times{maze.move}
		puts dir[maze.move]
		STDOUT.flush
	end
end