人材獲得作戦に応募してみた

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか の問題を解いてみた。

アルゴリズマーとしてはこの程度の問題20分で書けないとパソコン甲子園とかで辛いなあと思うのですが、40分でできました。

頭を使って解けるかどうかは知りませんが、知識としてこの程度の問題の解法を思いつける程度のものは持ってほしいですよね。

最短距離の算出は典型的なBFS。
最短ルートの特定はBFS深度を記憶して逆から探索する方法で、これはEdmonds-Karpで必要となる。

#include <cstdio>
#include <string>
#include <deque>
#include <vector>
#include <utility>

using namespace std;

int main(int argc, char **argv)
{
    vector<vector<int> > table;
    int sx,sy,gx,gy;
    for(int y = 0; !feof(stdin); y++) {
        table.push_back(vector<int>());
        for(int x = 0;; x++) {
            int ch = getchar();
            if(ch==-1 || ch=='\n')break;
            if(ch==' ') {
                table.back().push_back(0);
            } else if(ch=='S') {
                sx=x;sy=y;
                table.back().push_back(-1);
            } else if(ch=='G') {
                gx=x;gy=y;
                table.back().push_back(-2);
            } else if(ch=='*') {
                table.back().push_back(-3);
            }
        }
        if(table.back().size()==0){table.pop_back();break;}
    }
    deque<pair<int, pair<int, int> > > que;
    que.push_back(make_pair(1, make_pair(sx, sy)));
    while(!que.empty()) {
        int cd=que.front().first;
        int cy=que.front().second.first;
        int cx=que.front().second.second;
        que.pop_front();
        try{
            if(table.at(cy).at(cx) <= 0 &&
                    table.at(cy).at(cx) >= -2) {
                table.at(cy).at(cx) = cd;
                que.push_back(make_pair(cd+1, make_pair(cy,cx+1)));
                que.push_back(make_pair(cd+1, make_pair(cy,cx-1)));
                que.push_back(make_pair(cd+1, make_pair(cy+1,cx)));
                que.push_back(make_pair(cd+1, make_pair(cy-1,cx)));
            }
        }catch(...){}
    }
    {
        int x=gx, y=gy;
        while(x!=sx || y!=sy) {
            int cd=table.at(y).at(x);
            table.at(y).at(x)=-4;
            cd--;
            try{if(table.at(y).at(x-1)==cd) {
                x--;continue;
            }}catch(...){}
            try{if(table.at(y).at(x+1)==cd) {
                x++;continue;
            }}catch(...){}
            try{if(table.at(y-1).at(x)==cd) {
                y--;continue;
            }}catch(...){}
            try{if(table.at(y+1).at(x)==cd) {
                y++;continue;
            }}catch(...){}
            break;
        }
    }
    for(int y = 0; y < table.size(); y++) {
        for(int x = 0; x < table[y].size(); x++) {
            int state = table[y][x];
            if(sx==x && sy==y) {
                putchar('S');
            } else if(gx==x && gy==y) {
                putchar('G');
            } else if(state>=0) {
                putchar(' ');
            } else if(state==-3) {
                putchar('*');
            } else if(state==-4) {
                putchar('$');
            }
        }
        puts("");
    }
    return 0;
}

**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

ところでこの方は僕の先輩にあたる方なんですね。尊敬します。まあ普段WindowsではPuTTY使うんですが。

追記:言い訳

入出力の実装手段に迷って時間かかりました。最初iostream使おうと思ってreadlineがないことに気付いてやめてstdioにして文字のまま処理するよう実装しようと試みてやっぱやめたり、あと複数のスタートゴールに対応した実装にしようかと思ってやめたりしたのが原因。