白俊-3109号(パン屋さん)

15797 ワード
baekjoon テキストリンク
質問元:https://www.acmicpc.net/problem/3109
質問する

  • 有名なパン屋の金元雄(キム・ウォンウン)さんがパン屋を経営している.元雄のパン屋は世界的な財政危機を避けることができず、深刻な財政危機に陥った.

  • 元雄は支出を減らすために、あちこち見ていたところ、ガス代が一番大きいことに気づいた.そのため、元雄は近くのパン屋のガスパイプにこっそりパイプを設置し、盗んで使うことにした.

  • パン屋さんがあるところはR*Cメッシュで表示できます.1列目は近くのパン屋さんのガスパイプ、最後の列は元雄のパン屋さん.

  • 元雄はガスパイプとパン屋をつなぐパイプを取り付ける.パン屋とガスパイプの間に建物があるかもしれません.建物があれば、パイプを置くことはできません.

  • ガスパイプとパン屋を結ぶすべてのパイプラインは、最初の列から始まり、最後の列から終わらなければなりません.各セルは、右上隅、右上隅、右下隅に接続され、各セルの中心間で接続されます.

  • 元雄はできるだけ多くのガスを盗もうとした.そのため、ガスパイプとパン屋を結ぶパイプラインを複数設置する.この経路は重なり合ったり、つながったりすることはできません.つまり、各格子を通るパイプは1つでなければなりません.

  • 元雄がパン屋の様子を見たとき、元雄が取り付けられるガスパイプとパン屋を結ぶパイプラインの最大個数を求めるプログラムを作成してください.
    • import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static int[][] directions = {
            { -1, 1 }, // 오른쪽 위
            { 0, 1 },  // 오른쪽
            { 1, 1 },  // 오른쪽 아래
    };

    private static boolean result;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int R = Integer.parseInt(tokenizer.nextToken()); // 행
        int C = Integer.parseInt(tokenizer.nextToken()); // 열
        char[][] matrix = new char[R][C]; // 배열 생성
        for (int i = 0; i < R; i++) {
            matrix[i] = reader.readLine().toCharArray();
        }

        int ans = 0; // 파이프라인 갯수

        for (int i = 0; i < R; i++) {
            result = false; // 플래그 초기화
            recursive(matrix, i, 0, R, C);
            if (result) ans++; // 파이프라인이 완성된 경우 카운트 증가
        }

        System.out.println(ans);
    }

    // 백트래킹
    private static void recursive(char[][] matrix, int row, int col, int R, int C) {
        // 앞에서 가능한 수인지 체크를 하고 넘긴다.
        if (col == C - 1) {
            result = true;
            matrix[row][col] = 'x';
            return;
        }

        // 첫 열에서 시작
        matrix[row][col] = 'x';

        for (int j = 0; j < 3; j++) {
            int dy = row + directions[j][0];
            int dx = col + directions[j][1];

            if (dy >= 0 && dy < R && dx >= 0 && dx < C) {
                if (matrix[dy][dx] != 'x') recursive(matrix, dy, dx, R, C);
                if (result) break;
            }
        }
    }

}
  • DFSを利用した問題です.可能な道が見つかったら、最後の列に移動し、パイプラインが完了したらbooleanflagで戻りを停止します.
  • は、可能な限り数を見つけることができるわけではありません.パイプラインを完了すると、終了する必要がある部分を見逃しやすくなります.
    • 120.OkHttpのGetパラメータ接合
    純粋な JavaScript でダーク モード機能を作成する