[BOJ]2665号:迷宮を作る(C++)

26896 ワード
cpp algorithm baekjoon テキストリンク
質問リンク:白俊2665号です。
[質問へのアクセス]
最初は再帰で黒部屋を白部屋に変えてBFSを迂回したところタイムアウト.
悩んだあげく、黒室にいる間にcntを増やして、白室にいる間にこのようにして、その部屋に来たときにcnt値を比較しながら、最小値を更新し続けると(n,n)、黒室の最小個数を変えるだけで行の結果を保存することができます.(ちょっと多芸っぽい感じ?)
アルゴ駅問題とよく似ており、拡張問題でbigoをさらに短縮することができます.
[ソースコード]
BFS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
int arr[51][51];
int visit[51][51];
int n;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

void BFS() {
    queue<pair<int, int> > q;
    q.push(make_pair(1, 1));
    memset(visit, 10000, sizeof(visit));
    visit[1][1] = 0;

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0 ; i<4 ; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<=0 || nx>n || ny<=0 || ny>n) continue;
            
            // arr[nx][ny]가 0일 때는 cnt를 증가시켜야하고 1일때는 증가시키지 말아야한다.
            int tmp = 1-arr[nx][ny];
            
            if(visit[nx][ny] > visit[x][y] + tmp) {
                visit[nx][ny] = visit[x][y] + tmp;
                q.push(make_pair(nx,ny));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1 ; i<=n ; i++) {
        string s;
        cin >> s;
        for(int j=1 ; j<=s.size() ; j++) {
            arr[i][j] = s[j-1] - '0';
        }
    }
    BFS();
    cout << visit[n][n] << "\n";
}
ダエストラ
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
int arr[51][51];
int visit[51][51];
int n;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

typedef pair<int, pair<int, int> > p;

void BFS() {
    priority_queue<p, vector<p>, greater<p> > pq;
    pq.push(p(0, make_pair(1, 1)));
    memset(visit, 10000, sizeof(visit));
    visit[1][1] = 0;

    while(!pq.empty()) {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();

        if(x==n && y==n) return;

        for(int i=0 ; i<4 ; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<=0 || nx>n || ny<=0 || ny>n) continue;
            int tmp = 1-arr[nx][ny];
            if(visit[nx][ny] > visit[x][y] + tmp) {
                visit[nx][ny] = visit[x][y] + tmp;
                pq.push(p(visit[nx][ny], make_pair(nx,ny)));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1 ; i<=n ; i++) {
        string s;
        cin >> s;
        for(int j=1 ; j<=s.size() ; j++) {
            arr[i][j] = s[j-1] - '0';
        }
    }
    BFS();
    cout << visit[n][n] << "\n";
}
AndroidでのEGLの使用手順
Ramdaはあなたの友人です