[PYTHON] Vous marchez en spirale dans un monde où les murs de la croix s'élèvent (simulation)

À propos de l'entrée et de la sortie

Toutes les réponses suivantes utilisent des entrées / sorties standard, j'ai donc besoin d'un outil de notation. https://github.com/cielavenir/procon/blob/498c9856ea73bf871c15575e2d21bae7263d1167/hena/tyama_hena_validator.rb Exécutez avec hena_validator.rb hena28.py 28.

Cependant, vous pouvez poser des questions supplémentaires telles quelles sans utiliser l'outil de notation.

Méthode Right (Python / Ruby / C ++)

Il existe une bonne méthode en tant qu'algorithme pour résoudre le labyrinthe. S'il n'y a qu'un seul mur (topologiquement), vous devez marcher sans relâcher votre main droite pour atteindre l'objectif. Cela correspond à toujours essayer de tourner à droite vu du sens de la marche.

CheckiO a un problème avec Festival des lanternes. La question de répondre au nombre de cellules qui brillent actuellement au rinçage de la lanterne Cela peut également être résolu par la bonne méthode, donc cette fois j'ai utilisé la classe Maze. Par conséquent, le langage principal cette fois est Python. La version Ruby en est un portage.

La version C ++ de l'algorithme de CodeIQ de cette semaine Meet in the maze? .

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);
	}
}

Une autre solution pour la simulation (Ruby)

Habituellement, lorsque vous résolvez un labyrinthe, souvenez-vous de la direction à laquelle vous faites face. Cependant, cette fois, il n'y a pas de ** bosses sur la figure **, il est donc possible de résoudre le problème sans enregistrer la direction dans laquelle il fait face. Une stratégie pour se tenir un peu et tenir la direction du mur. Il y a une régularité dans cette «direction». Il est facile de comprendre si vous utilisez le cas-quand.

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