TopCoder SRM 735 Div 2 Med - TeleportationMaze

問題概要

通路が"."，壁が"#"で表される最大50×50の迷路がある．スタート地点$ (r_1, c_1) $からゴール地点$ (r_2, c_2) $に行くまでの所要時間を求める．

ただし，"."のある地点から4近傍の"."に移動するのに1秒かかる．また，今いる"."と同じ行または同じ列で，もっとも近い"."にワープすることができるが，これには2秒かかる．

解法概要

BFSで探索すればよいというのはすぐに思いついたが，実装の考察が甘くてシステスで落とされてしまった． とりあえず私が引っかかったのは以下の2点

• グローバル変数として定義した配列usedがfalseで初期化されるものと思い込んでいた (実際はtrueで初期化されていた)
• 訪れた座標に対するused[y][x]をtrueにする処理を，その座標をqueにpushするタイミングでやってしまっていた (そうすると，"その座標"にたどり着くより所要時間の短いコースがあったとしてもpriority_queueに入れる処理をしなくなってしまう)

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

bool used[50][50];

class TeleportationMaze {
    public:
    int pathLength(vector<string> a, int r1, int c1, int r2, int c2) {
        priority_queue< pair<int, Pii> > que;
        que.push(pair<int, Pii>(0, Pii(r1, c1)));
        int y = r1, x = c1;

        int ret = INT_MAX;
        fill(used[0], used[50], false);
        while(!que.empty()){
            pair<int, Pii> p = que.top(); que.pop();
            y = p.second.first;
            x = p.second.second;
            used[y][x] = true;
            if(y == r2 && x == c2){
                ret = min(ret, -p.first);
                continue;
            }
            
            int yy = y-1, cost;
            while(yy >= 0 && a[yy][x] == '#') yy--;
            if(!used[yy][x] && yy >= 0){
                if(yy == y-1) cost = p.first-1;
                else cost = p.first-2;
                que.push(pair<int, Pii>(cost, Pii(yy, x)));
            }
            yy = y+1;
            while(yy < int(a.size()) && a[yy][x] == '#') yy++;
            if(!used[yy][x] && yy < int(a.size())){
                if(yy == y+1) cost = p.first-1;
                else cost = p.first-2;
                que.push(pair<int, Pii>(cost, Pii(yy, x)));
            }
            int xx = x-1;
            while(xx >= 0 && a[y][xx] == '#') xx--;
            if(!used[y][xx] && xx >= 0){
                if(xx == x-1) cost = p.first-1;
                else cost = p.first-2;
                que.push(pair<int, Pii>(cost, Pii(y, xx)));
            }
            xx = x+1;
            while(xx < int(a[0].length()) && a[y][xx] == '#') xx++;
            if(!used[y][xx] && xx < int(a[0].length())){
                if(xx == x+1) cost = p.first-1;
                else cost = p.first-2;
                que.push(pair<int, Pii>(cost, Pii(y, xx)));
            }
        }
        return (ret==INT_MAX?-1:ret);
    }
};

所感

結構初歩的なミスをしてしまった

実装力のNASA of NASA