[白俊]17090号:迷宮を脱出

10288 ワード
白駿 supin2 cpp テキストリンク
回答日:2021-10-01

質問する


質問リンク:https://www.acmicpc.net/problem/17090

アクセスと解析


これはDPとDFSによるグラフィックブラウズの問題である.
問題の入力として,与えられた迷路のすべての位置からDFSを用いて探索を行い,脱出可能か否かを決定した.
探索の過程で重要なのは注釈の形式を利用することである.このため,dp配列が宣言され,dp配列はそのインデックスから出発したときに迷路から逃れることができるかどうかを指す.(dp[x][y]=1の場合、(x,y)から飛び出すことができる)
これを利用して,地図上の文字検索と同時にdp配列を更新した.
アクセス配列を最初に配置し、各場所でdfsを起動するたびにfalseに更新してナビゲートし、タイムアウトしました...

コード#コード#

// 백준 17090번 : 미로 탈출하기
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, M;
vector<string> maze;
int dp[501][501];

int dfs(int y, int x) {
    if (y < 0 || y >= N || x < 0 || x >= M) {
        return 1;
    }
    int &ret = dp[y][x];
    if (ret != -1) {
        return ret;
    }
    ret = 0;

    switch (maze[y][x]) {
        case 'U' :
            ret = dfs(y - 1, x);
            break;
        case 'R' :
            ret = dfs(y, x + 1);
            break;
        case 'D' :
            ret = dfs(y + 1, x);
            break;
        case 'L' :
            ret = dfs(y, x - 1);
            break;
    }
    return ret;
}

int main() {
    cin >> N >> M;
    
    string str = "";
    for (int i = 0; i < N; i++) {
        cin >> str;
        maze.push_back(str);
    }
    memset(dp, -1, sizeof(dp));

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (dfs(i, j) == 1) {
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

結果



フィードバック


似ているように見えますが、いろいろな問題があります.もっと多くの問題を作って,よく復唱しなければならない.
同時12:CountDownLatch、CyclicBarrier、Semaphore実装分析
[明日の学習キャンプ]#211118💻 TIL 💻