SRM 576 Div2 Med

問題

マリオのような2D横スクロールゲームの画面level(2次元配列)と、1枚のコインの座標が与えられる。(スクロールしない。)

マップの上から下に重力が働いていて、level[y][x]が'X'ならMonaoはその上に立つことができる。また、繋がっている足場へ歩いて移動することができ、長さLのはしごを使って真上、真下にある距離L以内の足場へ移動できる。 つまり、Monaoが(x,y)の位置にいるとき、(x±1,y),(x,y±l)(0<=l<=L)へ移動できる。 最も下の足場は地面であり、level.back()の行は全てXである。

初め、Monaoは最も下の足場に立っている。 コインがある場所まで行くために必要なはしごの長さの最小値を求めなさい。はしごが必要ないときは0を返しなさい。

解法

コインの場所までたどり着けるかどうかを、BFSをする関数ableでL=0の場合から順に判定し、たどり着けるようになった時のLを返しました。上位の人は2分探索していましたが、Lは高々50なのでこれで間に合いました。

実装

#include <algorithm>
#include <array>
#include <queue>
#include <stack>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

typedef pair<char,char> P;
bool ok[50][50]={};
queue<P> q;

bool able(int len, const vector<string>& floor,
          int r, int c, int w, int h){
    rep(i,h) ok[i].fill(false);
    q = queue<P>();
    q.push(P(0,h-1));
    while(q.size()){
        P p=q.front();
        vector<P> next;
        q.pop();
        const int qx=p.first, qy=p.second;
        if(qy==r&&qx==c) return true;
        ok[qy][qx]=true;
        int lx=qx-1;
        if(lx>=0 && !ok[qy][lx] && floor[qy][lx]=='X'){
            next.push_back(P(lx,qy));
        }
        int rx=qx+1;
        if(rx<w && !ok[qy][rx] && floor[qy][rx]=='X'){
            next.push_back(P(rx,qy));
        }
        loop(i,1,len+1){
            int uy=qy-i;
            if(uy>=0 && !ok[uy][qx] && floor[uy][qx] =='X'){
                next.push_back(P(qx,uy));
            }
            int dy=qy+i;
            if(dy<h && !ok[dy][qx] && floor[dy][qx] =='X'){
                next.push_back(P(qx,dy));
            }
        }
        random_shuffle(all(next));
        rep(i,next.size()){q.push(next[i]);}
    }
    return false;
}

class ArcadeManao {
public:
    int shortestLadder(const vector <string> floor,
                       int r, int c) {
        r--;c--;
        int w=floor[0].size();
        int h=floor.size();
        rep(i,50) if(able(i,floor,r,c,w,h)) return i;
    }
};

感想

次に訪れる点をキューに入れる前にrandom_shuffle(all(next))でシャッフルしています。システムテストのケースに、levelの全ての要素がXかつコインの位置が(0,0)であるようなケースがあり、WPFで(0,0)から探索し始めるのが最後になってしまって落ちたのですが、こうすると通りました。あとで再帰で書いたらそんなことしなくても余裕でしたが...