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

AtCoder ABC 054 A&B&C AtCoder - 054

A problem

--Compare the numbers of A and B --2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1 --Draw if the number is the same ――1 is the strongest, so if either one is 1, the other wins ――If it is neither the same number nor 1, the larger number wins

		int alice = nextInt();
		int bob = nextInt();

		if (alice == bob) {
			out.println("Draw");
		} else if (alice == 1) {
			out.println("Alice");
		} else if (bob == 1) {
			out.println("Bob");
		} else if (alice != bob) {
			out.println(alice > bob ? "Alice" : "Bob");
		}

		out.println("");

B problem

Description is written inline in the source

	private void solveB() {
		int numN = nextInt();
		int numM = nextInt();
		String[] wkA = new String[numN];
		String[] wkB = new String[numM];

		for (int i = 0; i < wkA.length; i++) {
			wkA[i] = next();
		}
		for (int i = 0; i < wkB.length; i++) {
			wkB[i] = next();
		}

		boolean res = chkB(wkA, 0, wkB, 0);
		out.println(res ? "Yes" : "No");
	}


	private boolean chkB(String[] wkA, int currentA, String[] wkB, int aPos) {
		boolean res = false;

		//Cannot search if wkA has less than wkB remaining
		if (wkA.length - currentA < wkB.length) {
			return false;
		}
		//wkA[]Remaining length is wkB[]Cannot search if less
		if (wkA[currentA].length() - aPos < wkB[0].length()) {
			return false;
		}
		//First, determine the position of A
		//Therefore, check where the current B column of B appears in the current A column of A.
		//Get the value on the horizontal axis of A
		//* There is a possibility that multiple horizontal axes of A can be obtained.
		//Check where B's current B column appears in A's current A column
		boolean aPosWk = wkA[currentA].startsWith(wkB[0], aPos);
		if (aPosWk) {
			//When the horizontal axis of A appears, current A+From the horizontal axis of column 1, currentB in column B+Check if 1 appears

			for (int i = 0; i < wkB.length; i++) {
				res = wkA[currentA + i].startsWith(wkB[0 + i], aPos);
				if (!res) {
					break;
				}
			}

		}
		//If the horizontal axis of A does not appear, aPos+Search first column
		//If this aPos does not match, aPos+1 and search again
		if (!res) {
			//Column B currentB+If 1 does not appear, search the horizontal axis of A again
			int len = wkA[currentA].indexOf(wkB[0], aPos + 1);
			//Search again because there are still candidates in the row
			if (len >= 0) {
				res = chkB(wkA, currentA, wkB, len);
			}

		}

		//If aPos is non-zero, set the next currentId
		if (!res && aPos == 0) {
			//If the horizontal axis of A does not appear, currentA+Search the first line
			res = chkB(wkA, currentA + 1, wkB, 0);
		}
		return res;
	}

C problem

Undirected graph Reference: 1 Reference: 2

For the time being, input example 1 is expressed as an adjacency matrix.

Input 1

1 2 1 3 2 3

Convert (put True wherever you can go)

Since it is a directed graph, it is a symmetric matrix.

--First, convert the input to the target matrix --Substitute true where you can go --Generate a boolean [] with the same length as numN to memo the destination --The search itself is recursive --The first place has been visited

	private void solveC() {

		int numN = nextInt();
		int numM = nextInt();

		boolean[][] wk = new boolean[numN][numN];

		for (int i = 0; i < numM; i++) {
			int iA = nextInt();
			int iB = nextInt();
			wk[iA - 1][iB - 1] = true;
			wk[iB - 1][iA - 1] = true;
		}
		boolean[] visited = new boolean[numN];
		visited[0] = true;
		int res = chkSolveC(wk, 0, visited);
		out.println(res);
	}

--Recursion end condition --If you have already visited, add +1 and finish --Conditions to proceed --You can go up the adjacency matrix (true with wk [] []) & have not visited yet (false with visited [])

With recursion, I wanted to add +1 to currentI when calling chkSolveC, but if I think about it carefully, I take out the i where I can go in the adjacency matrix and pass it as the argument currentI, so +1 is unnecessary.

	private int chkSolveC(boolean[][] wk, int currentI, boolean[] visited) {

		boolean res = true;
		for (int i = 0; i < visited.length; i++) {
			if (!visited[i]) {
				res = false;
			}
		}
		if (res) {
			return 1;
		}

		int resCnt = 0;
		boolean[] wkG = wk[currentI];
		for (int i = 0; i < wkG.length; i++) {
			if (wkG[i] && !visited[i]) {
				visited[i] = true;
				resCnt += chkSolveC(wk, i, visited);
				visited[i] = false;
			}

		}

		return resCnt;
	}