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

AtCoder ABC 020 A&B&C AtCoder - 020

** 2019/05/16 ** --Addition of problem name

A --Quiz

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

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

B --Takahashi-kun and character string compression

	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 with DFS (Memoization Recursion)

The hypothetical solution is as follows

1. Shortest path calculation with Floyd-Warshall Floyd / Bellman Ford / Dijkstra
2. Narrow down t by binary search

At first I thought about it in the same way as the assumed solution method, so I implemented it with Worshall Floyd, but even though it passes through sample or my assumed test case, when I actually throw it to the judge, about a quarter becomes WA. , I don't know the reason for WA, so I gave up and implemented it in DFS. I have to solve it somewhere again with the assumed solution method. 　 ** If you are a Floyd-Warshall Floyd, please tell me the point that someone really looks at the source and becomes WA **

A memorandum when implemented with memoization recursion (TLE countermeasures)

--Some of the implementation methods that are taken for granted are slower than expected. ――At first, it was TLE all the time, so as a result of verifying while modifying some code, TLE could be solved at once just by stopping the following (actually, while modifying it, it may be void without a return value. However, setting it to void was also subtly effective.)

--Stop using Long # min () --Dramatically improved speed when updating memo (dist [] []) stopped comparing memo contents by min --The TLE could be resolved by just modifying the source so that it stopped looking at Long # min () when updating the value of dist [] [](so that you don't have to do 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) {

		/*
		 *Exceeding the search range
		 *Or
		 *Already searched
		 */
		if (currentH < 0 || currentH >= h || currentW < 0 || currentW >= w || pass[currentH][currentW]) {
			return;
		}

		/*
		 *No further search required if the current value is less than the value already contained
		 *No further search required if the current value exceeds t
		 */
		if (dist[currentH][currentW] < val || val > t) {
			return;
		} else {
			/*
			 *Update the value because it is a search target
			 *I really want to set it to min, but I can't make it in time
			 */
			dist[currentH][currentW] = val;
		}
		/*
		 *Because it is G, it ends
		 */
		if (wk[currentH][currentW] == 'G' || (val > 0 && wk[currentH][currentW] == 'S')) {
			return;
		}
		pass[currentH][currentW] = true;
		/*
		 *Search in 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;
	}