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

AtCoder ABC 007 A&B&C AtCoder - 007

Vous aimerez peut-être les problèmes du passé parce qu'ils sont très instructifs. Problème C.

Calcul A-Ueki

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

		out.println(n - 1);
	}

Ordre du dictionnaire B

――Si vous avez seulement besoin de considérer l'ordre du dictionnaire, vous devez toujours mettre "a". --Si l'entrée est "a", sortie -1 car rien n'est plus petit que "a" dans l'ordre lexical.

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

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

Recherche de priorité C-Width

• Problèmes éducatifs de la recherche de priorité de largeur (BFS)

Site de référence

• 01-Une petite explication polie de BFS
• Introduction à l'algorithme de recherche complète
• Competition Pro Memorandum: Depth Priority Search, Width Priority Search Summary
• DP à recevoir et DP à distribuer, récurrence de mémo, problème de sac à dos sans limite de nombre
• Recherche de priorité de profondeur et recherche de priorité de largeur

Il est préférable de lire le site de référence

	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;
		/*
		 *Puisqu'il est utilisé comme file d'attente (LIFO), 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 car il est utilisé comme file d'attente (LIFO)()
			 */
			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;
						/*
						 *Puisqu'il est utilisé comme file d'attente (LIFO), addLast()
						 */
						que.addLast(newC);
						memo[wkX][wkY] = true;
					}
				}
			}
		}
		return -1;
	}