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

AtCoder ABC 020 A&B&C AtCoder - 020

** 2019/05/16 ** - Ajout du nom du problème

Un quiz

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

		out.println(n == 1 ? "ABC" : "chokudai");
	}

B --Takahashi-kun et compression de chaînes de caractères

	private void solveB() {
		String res = IntStream.range(0, 2).mapToObj(i -> next()).collect(Collectors.joining());

		out.println(Integer.parseInt(res) * 2);
	}

C --Wall through: AC avec DFS (Memo Recursive)

La solution hypothétique est la suivante

1. Calcul de l'itinéraire le plus court avec Worshall Floyd / Bellmanford / Dyxtra
2. Affiner t par dichotomie

Au début, j'y ai pensé de la même manière que la méthode de solution supposée, donc je l'ai implémentée avec Worshall Floyd, mais même si cela passe par un échantillon ou mon cas de test supposé, lorsque je le lance réellement au juge, environ un quart devient WA. , Je ne connais pas la raison de WA, alors j'ai abandonné et mis en œuvre avec DFS. Je dois encore le résoudre quelque part avec la méthode de solution supposée. 　 ** Si vous êtes un Worshall Floyd, dites-moi s'il vous plaît que quelqu'un regarde vraiment la source et devient WA **

Un mémorandum lorsqu'il est mis en œuvre par conversion de mémo (contre-mesures TLE)

―― Certaines des méthodes de mise en œuvre considérées comme acquises sont plus lentes que prévu. --Au début, c'était TLE tout le temps, donc à la suite de la vérification tout en modifiant du code, TLE pouvait être résolu à la fois juste en arrêtant ce qui suit (en fait, en le modifiant, il peut être nul sans valeur de retour. Mais c'était subtilement efficace pour le rendre nul)

• Arrêtez d'utiliser Long # min ()
• Amélioré considérablement lors de la mise à jour du mémo (dist [] []) et de l'arrêt de la comparaison du contenu du mémo par min --TLE pourrait être résolu simplement en modifiant la source pour arrêter de regarder Long # min () lors de la mise à jour de la valeur de dist [] [](afin que vous n'ayez pas à faire min ())

	private void solveC() {
		int h = nextInt();
		int w = nextInt();
		long t = nextLong();
		char[][] wk = new char[h][w];

		int sX = 0;
		int sY = 0;
		int gX = 0;
		int gY = 0;
		for (int i = 0; i < wk.length; i++) {
			wk[i] = next().toCharArray();
			for (int j = 0; j < wk[i].length; j++) {
				if (wk[i][j] == 'S') {
					sX = i;
					sY = j;
				} else if (wk[i][j] == 'G') {
					gX = i;
					gY = j;
				}
			}
		}
		long low = 1;
		long high = t;
		long[][] memo = new long[h][w];

		while (high - low != 1) {
			long mid = (high + low) / 2;
			for (long[] l : memo) {
				Arrays.fill(l, Long.MAX_VALUE);
			}
			dfsC(wk, h, w, t, sX, sY, mid, 0, memo, new boolean[h][w]);
			if (memo[gX][gY] <= t) {
				low = mid;
			} else {
				high = mid;
			}
		}

		out.println(low);
	}


	static final int[] dx = new int[] { 0, 0, -1, 1 };
	static final int[] dy = new int[] { 1, -1, 0, 0 };

	private void dfsC(char[][] wk, int h, int w, long t, int currentH, int currentW, long x, long val,
			long[][] dist, boolean[][] pass) {

		/*
		 *Dépassement de la plage de recherche
		 *Ou
		 *Déjà recherché
		 */
		if (currentH < 0 || currentH >= h || currentW < 0 || currentW >= w || pass[currentH][currentW]) {
			return;
		}

		/*
		 *Aucune recherche supplémentaire n'est requise si la valeur actuelle est inférieure à la valeur déjà dans
		 *Aucune recherche supplémentaire n'est requise si la valeur actuelle dépasse t
		 */
		if (dist[currentH][currentW] < val || val > t) {
			return;
		} else {
			/*
			 *Mettez à jour la valeur car il s'agit d'une cible de recherche
			 *Je veux vraiment le régler sur min, mais je ne peux pas le faire à temps
			 */
			dist[currentH][currentW] = val;
		}
		/*
		 *Parce que c'est G, ça se termine
		 */
		if (wk[currentH][currentW] == 'G' || (val > 0 && wk[currentH][currentW] == 'S')) {
			return;
		}
		pass[currentH][currentW] = true;
		/*
		 *Rechercher dans 4 directions
		 */
		for (int i = 0; i < 4; i++) {
			int wkH = currentH + dx[i];
			int wkW = currentW + dy[i];
			if (wkH < 0 || wkH >= h || wkW < 0 || wkW >= w) {
				continue;
			}
			long currVal = 0;
			switch (wk[wkH][wkW]) {
			case 'S':
			case 'G':
			case '.':
				currVal = 1;
				break;
			case '#':
				currVal = x;
				break;
			default:
				break;
			}

			dfsC(wk, h, w, t, wkH, wkW, x, val + currVal, dist, pass);
		}
		pass[currentH][currentW] = false;
	}