C++で経路探索

事の始まりは某所のC#スレで見かけたこの記事。ちょこっと引用すると、

内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。
たとえば、S:スタート　G:ゴール　*:壁　$:解答の経路　としたとき、

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

とのこと。ふむ、なかなか面白そうじゃない！　独りでやるのも寂しいので、学校の先生と競争してみることに。

#include <iostream>
#include <string>
#include <fstream>
#include <vector>

typedef unsigned char byte;
typedef unsigned int uint;
typedef std::vector<std::string> StringList;

using namespace std;

/**
* 2次元配列の位置などを表す構造体
*/
struct POS{
    uint x, y;
};

//定数
const char *fname = "dat.txt";//ファイルデータパス
const byte WALL = -1;//壁を表す定数

//
// 再帰的にスタートからゴールへ向かって最短距離を求める
// @param now 現在位置
// @param from 一つ前の位置
// @param dat 書き換えるデータ配列
// @param width データ配列幅
// @param start スタート地点
// @param goal ゴール地点
// @return none
//
void SearchPath(
                uint count,
                const POS &now,
                const POS &from,
                byte *dat,
                uint width,
                const POS &start,
                const POS &goal
                )
{
    //再帰の終了をチェック
    if(now.x == goal.x && now.y == goal.y){
        dat[now.x+now.y*width] = count+1;
    }

    //次に移動する座標を決定する
    POS next[4] ={
        {now.x, now.y-1},//上
        {now.x, now.y+1},//下
        {now.x-1, now.y},//左
        {now.x+1, now.y},//右
    };
    for(uint i=0; i<4; ++i){
        uint idx = next[i].x + next[i].y*width;//次に調べる位置

        //次の位置が壁なら調べない
        if(dat[idx] == WALL){
            continue;
        }

        //次に調べる位置が既に調べてあり
        //かつ、すでに最短パスが出ていたらこれ以上調べない
        if(dat[idx] > 0 && dat[idx] < count){
            continue;
        }

        //現在の位置にこれまでの歩数を記録する
        dat[now.x+now.y*width] = count;

        //次の経路を再帰的に調べる
        SearchPath(count+1, next[i], now, dat, width, start, goal);
    }
}

//
// ゴール地点からスタート地点へ向かって最短経路を描画する
// @param sl 書き出す文字列リスト
// @param now 現在位置への参照
// @param start スタート地点
// @param goal ゴール地点
// @param dat ステップ数が記述されたデータ配列（壁は0xff）
// @param width データ配列幅
//
void FindPath(
              StringList *sl,
              const POS &now,
              const POS &start,
              const POS &goal,
              const byte *dat,
              uint width
              )
{
    //再帰打ち切りの条件
    //すなわち、現在地がスタート地点なら終了
    if(now.x == start.x && now.y == start.y){
        return;
    }

    //次に移動する座標を決定する
    POS next[4] ={
        {now.x, now.y-1},//上
        {now.x, now.y+1},//下
        {now.x-1, now.y},//左
        {now.x+1, now.y},//右
    };

    //現在のステップ数
    uint nowStep = dat[now.x+now.y*width];

    for(uint i=0; i<4; ++i){
        uint idx = next[i].x + next[i].y*width;//次に調べる位置

        //次の位置が壁なら調べない
        if(dat[idx] == WALL){
            continue;
        }

        //次の位置が現在のステップ数より小さいときは
        //再帰的に調べる
        if(dat[idx] == nowStep-1){
            //経路マークをつける
            char mark = '$';
            if(now.x == goal.x && now.y == goal.y){
                mark = 'G';
            }
            sl->at(now.y).at(now.x) = mark;

            //次の経路を再帰的に調べる
            FindPath(sl, next[i], start, goal, dat, width);
            return;
        }
    }
}

//
//エントリポイント
//
int main(){
    //
    // テキストからデータを読み込んで配列に格納
    //
    std::fstream fs(fname);
    StringList sl;
    while(!fs.eof()){
        string tmp;
        getline(fs, tmp, '\n');
        sl.push_back(tmp);
    }

    //数値に変換して配列に格納
    uint height = sl.size();//配列高さ
    uint width = sl[0].size();//配列幅
    byte *dat = new byte [width*height];//作業用配列

    POS start = {0,0};//スタート
    POS goal = {0,0};//ゴール
    POS now = {0,0};//現在地

    for(uint y=0; y<height; ++y){
        for(uint x=0; x<width; ++x){
            uint idx = x+y*width;
            dat[idx] = 0;
            switch(sl[y][x]){
                case '*':
                    dat[idx] = WALL;
                    break;
                case 'G':
                    goal.x = x;
                    goal.y = y;
                    break;
                case 'S':
                    start.x = now.x = x;
                    start.y = now.y = y;
                    break;
            }
        }
    }

    //
    // 経路探索
    // 上下左右に対して再帰的に検索をかける
    //
    SearchPath(0, start, start, dat, width, start, goal);

    //探索したパスを元に最短経路を描画する
    FindPath(&sl, goal, start, goal, dat, width);

    //
    //デバグ用表示
    //
    for(uint y=0; y<sl.size(); ++y){
        cout << sl[y] << endl;
    }

    //
    //ファイル書き出し
    //
    ofstream ofs("out.txt");
    for(uint y=0; y<sl.size(); ++y){
        ofs << sl[y] << endl;
    }
    ofs.close();

    //あとしまつ
    delete [] dat;
    dat = 0;

    return 0;
}

結果は惨敗。相手は１時間ちょっとで終わっていたのに対して、私は４時間かけてようやくといったところ。先生はPythonを使われていいたようです。てかこの手の問題でC++を使う時点でダメだろ俺…。Pythonなどの高級言語や、関数型言語ならもっともっと美しく簡潔に書けたでしょうね。とにかく自分の無能さが身に染みてわかった。くやしい！

自分のアホさにげんなりした問題でした。さて、寝よう(：Ｄ)┼─┤