[JAVA] Ich habe das Problem der älteren Schwester tatsächlich im Code ausgedrückt und berechnet

Was ist das Problem mit deiner Schwester?

https://www.youtube.com/watch?v=Q4gTV4r0zRs ** "Wie man Fukashigi zählt" Mit deiner Schwester! Zählen wir zusammen! ** ** **

Dies ist ein Youtube-Video. Dies ist ein Video, in dem eine ältere Schwester, die die Explosion einer Kombination vermitteln möchte, ihr ganzes Leben damit verbringt, die Größe der Kombination zu lehren.

Das hier angesprochene Problem ist "Es gibt N x N Quadrate, und Sie können einen Umweg vom Start oben links zum Ziel unten rechts machen. Wie viele Richtungen können Sie also einschlagen?" Das ist. Jeder soll zählen, also bleibt ihm nichts anderes übrig, als zu zählen.

Die einzige Einschränkung besteht darin, dass Sie nicht denselben Weg gehen dürfen.

** Ich bin neugierig, also möchte ich es selbst überprüfen !! **.

Dieser Algorithmus

~~ Respektiere deine Schwester ~~ Verwende eine einfache Methode. Insbesondere im Fall von 2x2 ist das Urteil wie folgt. Hier zur Erklärung Beginnen Sie mit [0] [0] und beenden Sie mit [2] [2].

① Packen Sie zuerst [0] [0] in den Stapel ② Entfernen Sie [0] [0] vom Stapel ③ Entscheiden Sie, ob Sie nach oben gehen möchten. (Diesmal kann ich nicht fortfahren) ④ Entscheiden Sie, ob Sie nach unten gehen möchten. (Diesmal fortfahren) ⑤ Füllen Sie den Stapel mit Routen, die von [0] [0] → [1] [0] ausgehen. ⑥ Entscheiden Sie, ob Sie nach rechts gehen möchten. (Diesmal fortfahren) ⑦ Füllen Sie den Stapel mit Routen, die von [0] [0] → [0] [1] ausgehen. ⑧ Entscheiden Sie, ob Sie nach links gehen möchten. (Diesmal kann ich nicht fortfahren) ⑨ Zurück zu ②. (Wenn zu diesem Zeitpunkt der Stapel leer ist, endet der Prozess.)

Es ist ein sehr einfacher Algorithmus.

Lassen Sie die Route entscheiden

Ich wollte die objektorientierte Implementierung üben und habe sie daher auf der Grundlage dieser Richtlinie betrachtet.

Bei Implementierung wie ein Transaktionsskript "Diese Route hat diese Route genommen, sodass Sie nach rechts oder links gehen können." ** Menschliche Richter **,

"Route-Kun, kannst du nach rechts gehen?" "Ja" Bitten Sie sie zu entscheiden, ob die tatsächliche Route nach rechts oder nach links verlaufen kann.

Speziell

List<Integer> route = routeSet.getLatest();
if (route == (Ein Zustand)){
Rechts empfohlen
}

nicht

if (route.canGoLeft())

Lassen Sie die Route und die tatsächliche Bewegung entscheiden

route.goLeft();

Ich würde es gerne so umsetzen.

Quellcode

Ich habe es mit der Absicht geschrieben, die obige Route eine Entscheidung treffen zu lassen.

Ich wollte es so implementieren, dass die Bewegung intuitiv verstanden werden kann, ohne den Inhalt der Route-Klasse zu kennen. Ich wollte die Verarbeitung nach dem Verschieben der Route standardisieren, konnte mir aber keinen guten Namen vorstellen, und es wurde ein mysteriöser Methodenname wie 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 + "Straße");
		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);
	}
}

Als nächstes folgt die Implementierung der Route-Klasse. [0] [0] und zweidimensionales Array schienen also schwierig zu sein

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

Es wurde als eindimensionales Array verwaltet. (Dieses Mal wurde die Länge der Route nicht festgelegt und die Ausgabe schien schwierig zu sein, also habe ich ArrayList verwendet, obwohl es schwer ist ...)

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

Ich denke, es ist ein bisschen überflüssig, aber ich denke, dass der Vorteil, den Anrufer von Route verstehen zu können, größer ist.

Machen wir das!

Die 2x2-Ausgabe sieht folgendermaßen aus: Ob es erfolgreich war, verschiedene Urteile über die Punkte zu fällen, es funktionierte vom ersten Schuss an richtig.

Ich habe aus der Erkenntnis gelernt, dass die Objektorientierung umso stärker ist, je komplizierter die Logik ist.

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 Möglichkeiten
1ms

Stoppen Sie die Ausgabe für jede Route (da die E / A hier viel Zeit in Anspruch zu nehmen schien) Das Ergebnis der Ausführung ist wie folgt. ~~ 7 wird überprüft. ~~

Impressionen

――Ich konnte den Effekt beim Üben der Objektorientierung spüren. ――Es ist noch neu, aber ich finde es erstaunlich, dass ein Computer in realistischer Zeit fast 600 Millionen Routen berechnen kann. ――Ich habe die Kombinationsexplosion erlebt. »Ich verstehe die Gefühle deiner Schwester.