ABC - 007 - A&B&C

AtCoder ABC 007 A&B&C

AtCoder - 007

過去の問題ってとっても教育的なものがあって好きかも。
C問題とか。

A - 植木算

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

        out.println(n - 1);
    }

B - 辞書式順序

• 辞書順だけ考慮すればいいのなら、常に"a"いれればいいよね
  • 入力が"a"の場合、辞書順で"a"より小さいものはないので-1を出力

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

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

C - 幅優先探索

• 幅優先探索（BFS）の教育的な問題

参考サイト

• 01-BFSのちょっと丁寧な解説
• 全探索アルゴリズム入門
• 競プロ覚書：深さ優先探索，幅優先探索 まとめ
• 貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題
• 深さ優先探索と幅優先探索

参考サイトを一通り読むのが一番

    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;
        /*
         * Queu（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()) {
            /*
             * Queu（LIFO）として使うのでremoveFirst()
             */
            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;
                        /*
                         * Queu（LIFO）として使うのでaddLast()
                         */
                        que.addLast(newC);
                        memo[wkX][wkY] = true;
                    }
                }
            }
        }
        return -1;
    }