BOJ 9205ビールを飲んで歩く

BOJ 9205は道を探す問題です.
決まった時間内に、ビールを飲みながら歩き、ビールが足りない前に、お店でビールを飲み続け、目的地が見つかるかどうかを印刷します.
に答える
ビールがお腹に入るまで歩ける最大距離は1000 mなので、BFSを利用して1000 m以内のスーパーを訪問し、目的地に着くかどうかを確認する方法を解きました.

using namespace std;

bool canWalk(pair<int,int> &a, pair<int,int> &b) {
    return abs(a.first - b.first) + abs(a.second - b.second) <= 1000;
}

void bfs(vector<pair<int,int>> &a) {
    vector<bool> visited(a.size());
    queue <int> q;
    q.push(0);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        visited[curr] = true;
        for (int i = 1; i < a.size(); i++) {
            if (!visited[i] && canWalk(a[curr], a[i])) {
                if (i == a.size() - 1) {
                    cout << "happy\n";
                    return;
                }
                q.push(i);
            }
        }
    }
    cout << "sad\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        vector<pair<int, int>> a(n + 2);

        for (int i = 0; i < n + 2; i++) {
            cin >> a[i].first >> a[i].second;       
        }

        bfs(a);        
    };
    
    return 0;
}

振り返る

なぜ正しいのか(なぜ正しいと言ったのに間違っているのか?)テスト例ごとに初期化を忘れています.ミスしないでね

実現

BFSは以前より少し速くなった.しかし、まだミスを犯す傾向がある.

TODO

ダエストラナフロイド・ワッシャーで解きましょう.以前は2つのアルゴリズムがよく用いられていたが,最近はより容易に実現できるBFSまたはDFSを用いて解決された問題が両者の1つであるため,迅速に実現することは困難である.

問に答える前に、複雑さを考慮した練習も必要らしい.

別の解釈

ブログ