[白俊]1261:アルゴ駅(JAVA)

18574 ワード
BFS memorization アルゴリズム#アルゴリズム# boj テキストリンク

質問する


BOJ1261:Algospot-https://www.acmicpc.net/problem/1261

に答える


少なくともどれだけ壁を割るかを求める必要があるので、まずBFSで可能な経路を見つけなければならないと思います.
[キュー内の条件]
  • はこの場所にアクセスしたことがない、または
  • 以前にアクセスしたことがあるが、現在アクセスしているアタッチメント壁がより少ない場合、
    • 2号条件を確認するためmapとは異なり,付身壁個数を計算するcntアレイを作製した.アクセスするかどうかだけでなく、数値を計算する必要があるため、-1に初期化するとアクセスしないことを示します.

    コード#コード#

    
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static class Loc{
        int i;
        int j;
        int cnt;

        public Loc(int i, int j, int cnt) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int m = Integer.parseInt(inputs[0]);
        int n = Integer.parseInt(inputs[1]);

        int[][] map = new int[n + 1][m + 1];
        int[][] cnt = new int[n + 1][m + 1]; // memorization

        for (int i = 1; i <= n; i++) {
            String tmp = br.readLine();
            for (int j = 1; j <= m; j++) {
                map[i][j] = Integer.parseInt(String.valueOf(tmp.charAt(j-1)));
                cnt[i][j] = -1;
            }
        }

        Queue<Loc> queue = new LinkedList<>();
        queue.add(new Loc(1, 1, 0));
        cnt[1][1] = 0; // start point

        int[] mi = {0, 0, -1, 1};
        int[] mj = {1, -1, 0, 0};

        while (!queue.isEmpty()) {
            Loc now = queue.poll();

            for (int d = 0; d < 4; d++) {
                int ni = now.i + mi[d];
                int nj = now.j + mj[d];

                if (ni < 1 || ni > n || nj < 1 || nj > m) {
                    continue;
                }
                int tmp_cnt = now.cnt;
                if(map[ni][nj]==1){
                    tmp_cnt++;
                }
                
                if(cnt[ni][nj] == -1 || cnt[ni][nj]>tmp_cnt){
                    cnt[ni][nj] = tmp_cnt;
                    queue.add(new Loc(ni, nj, tmp_cnt));
                }

            }
        }

        System.out.println(cnt[n][m]);

    }
}

    整理する


    ✔ 알고리즘 분류 - 그래프 이론, 다익스트라, 0-1 너비 우선 탐색
✔ 난이도 - 🟡 Gold 4

    🤦‍♀️ 今日のメッセージ


  • BFSは条件をどう与えるかよく考えるべきだ!訪問の有無だけを確認する場合もあれば、他のことも考えなければならない場合もありますので、問題をよく読んでください.

  • 質問を済ませてから探してみると、Priority QueueやDequeで答える方法もあるようですので、後で整理しましょう.

    • コメントサイト


    いいえ
    [C++]伯俊#11054:最も長い生物特徴部分数列
    FILOTチャットアプリケーション-1(モデル)の作成