[JAVA] ABC - 007 - A & B & C.

AtCoder ABC 007 A&B&C AtCoder - 007

Sie mögen vielleicht die Probleme der Vergangenheit, weil sie sehr lehrreich sind. C Problem.

A-Ueki-Berechnung

	private void solveA() {
		int n = nextInt();

		out.println(n - 1);
	}

B-Wörterbuch Reihenfolge

――Wenn Sie nur die Wörterbuchreihenfolge berücksichtigen müssen, sollten Sie immer "a" setzen.

• Wenn die Eingabe "a" ist, geben Sie -1 aus, da nichts in lexikalischer Reihenfolge kleiner als "a" ist.

	private void solveB() {
		String wk = next();

		if (wk.equals("a")) {
			out.println(-1);
		} else {
			out.println("a");
		}
	}

C-Breite Prioritätssuche

• Bildungsprobleme bei der Suche nach Breitenpriorität (BFS)

Referenzseite

• 01-Eine kleine höfliche Erklärung von BFS
• Einführung in den vollständigen Suchalgorithmus
• Competition Pro Memorandum: Suche nach Tiefenprioritäten, Zusammenfassung der Suche nach Breitenprioritäten
• DP zu empfangen und DP zu verteilen, Wiederholung zu Memo, Rucksackproblem ohne Begrenzung der Anzahl
• Suche nach Tiefenpriorität und Suche nach Breitenpriorität

Lesen Sie am besten die Referenzseite durch

	private void solveC2() {
		int r = nextInt();
		int c = nextInt();
		int sX = nextInt() - 1;
		int sY = nextInt() - 1;
		int gX = nextInt() - 1;
		int gY = nextInt() - 1;

		char[][] map = new char[r][c];
		for (int i = 0; i < r; i++) {
			map[i] = next().toCharArray();
		}
		Deque<Cordinate> que = new ArrayDeque<Cordinate>();
		Cordinate start = new Cordinate();
		start.x = sX;
		start.y = sY;
		start.step = 0;
		/*
		 *Da es als Warteschlange (LIFO) verwendet wird, addLast()
		 */
		que.addLast(start);
		boolean[][] memo = new boolean[r][c];
		memo[sX][sY] = true;
		int res = bfs(map, que, r, c, gX, gY, memo);

		out.println(res);
	}

	private static class Cordinate {
		private int x;
		private int y;
		private int step;
	}

	private static final int[] vX = { 1, 0, 0, -1 };
	private static final int[] vY = { 0, 1, -1, 0 };

	private int bfs(char[][] map, Deque<Cordinate> que, int r, int c, int gX, int gY, boolean[][] memo) {

		while (!que.isEmpty()) {
			/*
			 *RemoveFirst, da es als Warteschlange (LIFO) verwendet wird()
			 */
			Cordinate curr = que.removeFirst();
			if (curr != null) {
				if (curr.x == gX && curr.y == gY) {
					return curr.step;
				}
				for (int i = 0; i < 4; i++) {
					int wkX = curr.x + vX[i];
					int wkY = curr.y + vY[i];
					int step = curr.step + 1;
					if (wkX >= 0 && wkX < r && wkY >= 0 && wkY < c && map[wkX][wkY] != '#' && !memo[wkX][wkY]) {
						Cordinate newC = new Cordinate();
						newC.x = wkX;
						newC.y = wkY;
						newC.step = step;
						/*
						 *Da es als Warteschlange (LIFO) verwendet wird, addLast()
						 */
						que.addLast(newC);
						memo[wkX][wkY] = true;
					}
				}
			}
		}
		return -1;
	}