ABC - 075- A&B&C

AtCoder ABC 075 A&B&C

AtCoder - 075

A問題

• 地道に全て比較

	private void solveA() {
		int numA = nextInt();
		int numB = nextInt();
		int numC = nextInt();

		if (numA == numB) {
			out.println(numC);
		} else if (numA == numC) {
			out.println(numB);
		} else if (numB == numC) {
			out.println(numA);
		}
	}

B問題

• 文字をchar[]にしてloop
• '.'だったら、周囲8マス{$X=(1,0,-1),y=(1,0,-1)$}を探索し、周囲に存在する'#'の数に書き換える
• 出力

	private void solveB() {
		int numH = nextInt();
		int numW = nextInt();

		char[][] wk = IntStream.range(0, numH).map(i -> i).collect(() -> new char[numH][numW],
				(t, i) -> {
					t[i] = next().toCharArray();
				},
				(t, u) -> {
					Stream.concat(Arrays.stream(t), Arrays.stream(u));
				});

		StringBuilder builder = new StringBuilder();
		for (int j = 0; j < numH; j++) {
			builder.setLength(0);
			for (int k = 0; k < numW; k++) {
				if (wk[j][k] == '.') {
					int res = chkB(wk, j, k, numH, numW);
					builder.append(res);
				} else {
					builder.append(wk[j][k]);
				}
			}
			out.println(builder.toString());
		}

	}

	private int chkB(char[][] wk, int h, int w, int maxH, int maxW) {
		int[] CONST_H = new int[] { 1, 0, -1 };
		int[] CONST_W = new int[] { 1, 0, -1 };
		int res = 0;
		for (int i : CONST_H) {
			for (int j : CONST_W) {
				if (i == 0 && j == 0) {
					continue;
				}
				if (h + i >= 0 && h + i < maxH
						&& w + j >= 0 && w + j < maxW) {
					res += wk[h + i][w + j] == '#' ? 1 : 0;
				}
			}
		}
		wk[h][w] = (char) res;
		return res;
	}

C問題

効率の良い方法ではない。別の解は勉強中
今回は対象行列ということを利用した再帰で解いた。

橋の数をカウントしたい

• ある地点の辺が1個しかない場合

  • その辺は橋である

• ある地点の辺が2個以上の場合

  • 辺と橋が混在しているかもしれないし、辺のみかもしれない

• 初期時点では橋が特定できなくても、橋を削除していくと特定可能となる場合がある

解法はコードの中に直接コメントで記載

	private void solveC() {
		int numN = nextInt();
		int numM = nextInt();

		//隣接行列を作成しておく
		int[][] wk = IntStream.range(0, numM).collect(() -> new int[numN][numN],
				(t, i) -> {
					int startN = nextInt();
					int endN = nextInt();
					t[startN - 1][endN - 1] = 1;
					t[endN - 1][startN - 1] = 1;
				}, (t, u) -> {
					Stream.concat(Arrays.stream(t), Arrays.stream(u)).toArray();
				});

		out.println(chkC(numN, wk, 0, 0));
	}

	private int chkC(int numN, int[][] wk, int i, int totalCnt) {
		//iが最後までたどり着いたら終了
		if (i >= numN) {
			return totalCnt;
		}
		//地点iに存在する辺のリスト
		int[] wkArray = wk[i];
		int wkCnt = 0;
		int res = 0;
		int targetIndex = 0;
		//地点iの辺はいくつあるのか
		for (int j = 0; j < wkArray.length; j++) {
			if (wkArray[j] != 0) {
				wkCnt++;
				targetIndex = j;
			}
		}
		/*
		 * 1つしかない場合はその辺は橋であるので削除
		 * 複数あった場合は辺を特定できない
		 */

		if (wkCnt == 1) {
			//削除
			wk[i] = new int[numN];
			//隣接行列は対象性があるため、対象の地点の辺も削除
			wk[targetIndex][i] = 0;
			if (targetIndex < i) {
				/*
				 * 対象性があるので、index順で前の行列を削除した場合は其方を再度検索する
				 * もしかしたら、この削除によって辺が2つあったのが1つに減っているかもしれない
				 */
				res = chkC(numN, wk, targetIndex, totalCnt + 1);
			} else {
				/*
				 * index順で後ろのやつは、後で消すのでとりあえず先へ
				 */
				res = chkC(numN, wk, i + 1, totalCnt + 1);
			}
			return res;
		} else {
			/*
			 * この地点の辺を削除することは出来なかったので次の橋を探すために地点を進める
			 */
			return chkC(numN, wk, i + 1, totalCnt);
		}

	}