ABC --007 --A & B & C

AtCoder ABC 007 A&B&C AtCoder - 007

You may like the problems of the past because they are very educational. C problem.

A-Ueki calculation

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

		out.println(n - 1);
	}

B-Lexicographic order

――If you only need to consider the dictionary order, you should always enter "a". --If the input is "a", output -1 because nothing is smaller than "a" in dictionary order.

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

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

C-Breadth-first search

--Educational issues of breadth-first search (BFS)

Reference site

-01-A little polite explanation of BFS -Introduction to full search algorithm -Competition Pro Memorandum: Depth-first search, breadth-first search summary -DP to receive and DP to be distributed, recursion to memo, knapsack problem with no limit on the number -Depth-first search and breadth-first search

It is best to read through the reference site

	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;
		/*
		 *Since it is used as a Queue (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 because it is used as Queue (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;
						/*
						 *Since it is used as a Queue (LIFO), addLast()
						 */
						que.addLast(newC);
						memo[wkX][wkY] = true;
					}
				}
			}
		}
		return -1;
	}