[JAVA] J'ai en fait exprimé le problème de la sœur aînée dans le code et l'ai calculé

Quel est votre problème de sœur?

https://www.youtube.com/watch?v=Q4gTV4r0zRs ** "Comment compter Fukashigi" Avec votre sœur! Comptons ensemble! ** **

Ceci est une vidéo YouTube. Il s'agit d'une vidéo dans laquelle une sœur aînée qui veut transmettre l'explosion d'une combinaison passe toute sa vie à enseigner la grandeur de la combinaison.

Le problème abordé ici est "Il y a N x N carrés, et vous pouvez faire un détour depuis le début en haut à gauche vers le but en bas à droite, alors combien de directions pouvez-vous prendre?" C'est. On dit à tout le monde de compter, il n'y a donc pas d'autre choix que de compter.

La seule restriction est que vous ne devez pas suivre le même chemin.

** Je suis curieux, alors j'aimerais le vérifier moi-même !! **.

Cet algorithme

~~ Respectez votre sœur ~~ Utilisez une méthode simple. Plus précisément, dans le cas de 2x2, le jugement est le suivant. Ici, par souci d'explication Commencez par [0] [0] et terminez par [2] [2].

① Tout d'abord, mettez [0] [0] dans la pile ② Retirez [0] [0] de la pile ③ Décidez si vous voulez monter. (Je ne peux pas continuer cette fois) ④ Décidez s'il faut procéder à la baisse. (Continuez cette fois) ⑤ Remplissez la pile avec des routes qui procédaient de [0] [0] → [1] [0]. ⑥ Décidez s'il faut procéder à droite. (Continuez cette fois) ⑦ Remplissez la pile avec des routes qui procédaient de [0] [0] → [0] [1]. ⑧ Décidez si vous souhaitez procéder vers la gauche. (Je ne peux pas continuer cette fois) ⑨ Revenez à ②. (À ce moment-là, si la pile est vide, le processus se termine)

C'est un algorithme très simple.

Laissez la route décider

Je voulais m'entraîner à l'implémenter d'une manière orientée objet, alors je l'ai considéré comme basé sur cette politique.

Lorsqu'il est implémenté comme un script de transaction, "Cet itinéraire a emprunté cet itinéraire, vous pouvez donc aller à droite ou à gauche." ** Juges humains **,

"Route-kun, pouvez-vous aller à droite?" "Oui" Demandez-leur de décider si l'itinéraire réel peut aller à droite ou à gauche.

En particulier

List<Integer> route = routeSet.getLatest();
if (route == (Une certaine condition)){
Recommandé à droite
}

ne pas

if (route.canGoLeft())

Laissez l'itinéraire décider et le mouvement réel

route.goLeft();

Je voudrais l'implémenter comme ça.

Code source

Je l'ai écrit avec l'intention de laisser l'itinéraire ci-dessus prendre une décision.

J'avais l'intention de l'implémenter pour que le mouvement puisse être compris intuitivement sans être réellement conscient du contenu de la classe Route. Je voulais normaliser le traitement après avoir déplacé l'itinéraire, mais je ne pouvais pas penser à un bon nom, et cela a fini par être un nom de méthode mystérieux tel que postMoveProcess ...

import java.util.Scanner;
import java.util.Stack;

public class MazeSolver {

	private static long count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int len = sc.nextInt();
		sc.close();

		long start = System.nanoTime();
		Stack<Route> stack = new Stack<>();

		stack.add(new Route(len));

		while (stack.size() > 0) {
			Route route = stack.pop();
			if (route.canGoDown()) {
				Route clone = route.clone();
				clone.goDown();
				postMoveProcess(stack, clone);
			}
			if (route.canGoUp()) {
				Route clone = route.clone();
				clone.goUp();
				postMoveProcess(stack, clone);
			}
			if (route.canGoRight()) {
				Route clone = route.clone();
				clone.goRight();
				postMoveProcess(stack, clone);
			}
			if (route.canGoLeft()) {
				Route clone = route.clone();
				clone.goLeft();
				postMoveProcess(stack, clone);
			}
		}
		System.out.println(count + "rue");
		System.out.println(((System.nanoTime() - start) / 1000000) + "ms");
	}

	private static void postMoveProcess(Stack<Route> stack, Route route) {
		if (route.isGoal()) {
			route.printRoute();
			count++;
			return;
		}
		stack.add(route);
	}
}

Vient ensuite l'implémentation de la classe Route. [0] [0] et les tableaux bidimensionnels semblaient difficiles, donc

[0][0] → 0
[0][1] → 1
[0][2] → 2
[1][0] → 3
・ ・ ・
[2][2]→8

Il était géré comme un tableau unidimensionnel. (Cette fois, la longueur de l'itinéraire n'a pas été décidée et la sortie semblait difficile, j'ai donc utilisé ArrayList même si elle est lourde ...)

import java.util.ArrayList;

class Route implements Cloneable {

	private int len;

	private int goal;

	private ArrayList<Integer> route;

	private int location;

	Route(int len) {
		this.len = len + 1;
		this.route = new ArrayList<>();
		route.add(0);
		this.goal = (len + 1) * (len + 1) - 1;
		this.location = 0;
	}

	public boolean contains(int point) {
		return route.contains(point);
	}

	public boolean canGoUp() {
		int newLocation = location - len;
		if (newLocation < 0 || contains(newLocation)) {
			return false;
		}
		return true;
	}

	public void goUp() {
		int newLocation = location - len;
		if (!canGoUp()) {
			return;
		}
		move(newLocation);
	}

	public boolean canGoDown() {
		int newLocation = location + len;
		if (newLocation > goal || contains(newLocation)) {
			return false;
		}
		return true;
	}

	public void goDown() {
		int newLocation = location + len;
		if (!canGoDown()) {
			return;
		}
		move(newLocation);
	}

	public boolean canGoRight() {
		int newLocation = location + 1;
		if (newLocation % len == 0 || contains(newLocation)) {
			return false;
		}
		return true;
	}

	public void goRight() {
		int newLocation = location + 1;
		if (!canGoRight()) {
			return;
		}
		move(newLocation);
	}

	public boolean canGoLeft() {
		int newLocation = location - 1;
		if (location % len == 0 || contains(newLocation)) {
			return false;
		}
		return true;
	}

	public void goLeft() {
		int newLocation = location - 1;
		if (!canGoLeft()) {
			return;
		}
		move(newLocation);
	}

	private void move(int newLocation) {
		location = newLocation;
		route.add(newLocation);
	}

	public boolean isGoal() {
		return location == goal;
	}

	public void printRoute() {
		System.out.println(route.toString());
	}

	@SuppressWarnings("unchecked")
	@Override
	public Route clone() {
		Route clone = null;
		try {
			clone = (Route) super.clone();
			clone.route = (ArrayList<Integer>) this.route.clone();
		} catch (Exception e) {
			e.printStackTrace();
		}
		return clone;
	}
}

Je pense que c'est un peu redondant, mais je pense que l'avantage de pouvoir comprendre l'appelant de Route est plus grand.

Faisons le!

La sortie 2x2 ressemble à ceci: Que ce soit avec succès pour faire divers jugements sur les points, cela a fonctionné correctement dès le premier coup.

J'ai appris en réalisant que plus la logique est compliquée, plus l'orientation de l'objet est forte.

2
[0, 1, 2, 5, 8]
[0, 1, 2, 5, 4, 3, 6, 7, 8]
[0, 1, 2, 5, 4, 7, 8]
[0, 1, 4, 3, 6, 7, 8]
[0, 1, 4, 5, 8]
[0, 1, 4, 7, 8]
[0, 3, 4, 5, 8]
[0, 3, 4, 1, 2, 5, 8]
[0, 3, 4, 7, 8]
[0, 3, 6, 7, 8]
[0, 3, 6, 7, 4, 5, 8]
[0, 3, 6, 7, 4, 1, 2, 5, 8]
12 façons
1ms

Arrêtez la sortie pour chaque route (car l'IO ici semblait prendre beaucoup de temps) Le résultat de son exécution est le suivant. ~~ 7 est en cours de vérification. ~~

Impressions

«J'ai pu ressentir l'effet tout en pratiquant l'orientation objet. «C'est encore nouveau, mais je pense que c'est incroyable qu'un ordinateur puisse calculer près de 600 millions d'itinéraires dans un laps de temps réaliste. «J'ai vécu l'explosion de la combinaison. «Je comprends les sentiments de votre sœur.