2010年1月13日水曜日

C++で経路探索

事の始まりは某所のC#スレで見かけたこの記事。ちょこっと引用すると、
内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。
たとえば、S:スタート　G:ゴール　*:壁　$:解答の経路　としたとき、 
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
とのこと。ふむ、なかなか面白そうじゃない！　独りでやるのも寂しいので、学校の先生と競争してみることに。
view sourceprint?
001#include <iostream>
002#include <string>
003#include <fstream>
004#include <vector>
005 
006typedef unsigned char byte;
007typedef unsigned int uint;
008typedef std::vector<std::string> StringList;
009 
010using namespace std;
011 
012/**
013* 2次元配列の位置などを表す構造体
014*/
015struct POS{
016    uint x, y;
017};
018 
019//定数
020const char *fname = "dat.txt";//ファイルデータパス
021const byte WALL = -1;//壁を表す定数
022 
023//
024// 再帰的にスタートからゴールへ向かって最短距離を求める
025// @param now 現在位置
026// @param from 一つ前の位置
027// @param dat 書き換えるデータ配列
028// @param width データ配列幅
029// @param start スタート地点
030// @param goal ゴール地点
031// @return none
032//
033void SearchPath(
034                uint count,
035                const POS &now,
036                const POS &from,
037                byte *dat,
038                uint width,
039                const POS &start,
040                const POS &goal
041                )
042{
043    //再帰の終了をチェック
044    if(now.x == goal.x && now.y == goal.y){
045        dat[now.x+now.y*width] = count+1;
046    }
047 
048    //次に移動する座標を決定する
049    POS next[4] ={
050        {now.x, now.y-1},//上
051        {now.x, now.y+1},//下
052        {now.x-1, now.y},//左
053        {now.x+1, now.y},//右
054    };
055    for(uint i=0; i<4; ++i){
056        uint idx = next[i].x + next[i].y*width;//次に調べる位置
057 
058        //次の位置が壁なら調べない
059        if(dat[idx] == WALL){
060            continue;
061        }
062 
063        //次に調べる位置が既に調べてあり
064        //かつ、すでに最短パスが出ていたらこれ以上調べない
065        if(dat[idx] > 0 && dat[idx] < count){
066            continue;
067        }
068 
069        //現在の位置にこれまでの歩数を記録する
070        dat[now.x+now.y*width] = count;
071 
072        //次の経路を再帰的に調べる
073        SearchPath(count+1, next[i], now, dat, width, start, goal);
074    }
075}
076 
077//
078// ゴール地点からスタート地点へ向かって最短経路を描画する
079// @param sl 書き出す文字列リスト
080// @param now 現在位置への参照
081// @param start スタート地点
082// @param goal ゴール地点
083// @param dat ステップ数が記述されたデータ配列（壁は0xff）
084// @param width データ配列幅
085//
086void FindPath(
087              StringList *sl,
088              const POS &now,
089              const POS &start,
090              const POS &goal,
091              const byte *dat,
092              uint width
093              )
094{
095    //再帰打ち切りの条件
096    //すなわち、現在地がスタート地点なら終了
097    if(now.x == start.x && now.y == start.y){
098        return;
099    }
100 
101    //次に移動する座標を決定する
102    POS next[4] ={
103        {now.x, now.y-1},//上
104        {now.x, now.y+1},//下
105        {now.x-1, now.y},//左
106        {now.x+1, now.y},//右
107    };
108 
109    //現在のステップ数
110    uint nowStep = dat[now.x+now.y*width];
111 
112    for(uint i=0; i<4; ++i){
113        uint idx = next[i].x + next[i].y*width;//次に調べる位置
114 
115        //次の位置が壁なら調べない
116        if(dat[idx] == WALL){
117            continue;
118        }
119 
120        //次の位置が現在のステップ数より小さいときは
121        //再帰的に調べる
122        if(dat[idx] == nowStep-1){
123            //経路マークをつける
124            char mark = '$';
125            if(now.x == goal.x && now.y == goal.y){
126                mark = 'G';
127            }
128            sl->at(now.y).at(now.x) = mark;
129 
130            //次の経路を再帰的に調べる
131            FindPath(sl, next[i], start, goal, dat, width);
132            return;
133        }
134    }
135}
136 
137//
138//エントリポイント
139//
140int main(){
141    //
142    // テキストからデータを読み込んで配列に格納
143    //
144    std::fstream fs(fname);
145    StringList sl;
146    while(!fs.eof()){
147        string tmp;
148        getline(fs, tmp, '\n');
149        sl.push_back(tmp);
150    }
151 
152    //数値に変換して配列に格納
153    uint height = sl.size();//配列高さ
154    uint width = sl[0].size();//配列幅
155    byte *dat = new byte [width*height];//作業用配列
156 
157    POS start = {0,0};//スタート
158    POS goal = {0,0};//ゴール
159    POS now = {0,0};//現在地
160 
161    for(uint y=0; y<height; ++y){
162        for(uint x=0; x<width; ++x){
163            uint idx = x+y*width;
164            dat[idx] = 0;
165            switch(sl[y][x]){
166                case '*':
167                    dat[idx] = WALL;
168                    break;
169                case 'G':
170                    goal.x = x;
171                    goal.y = y;
172                    break;
173                case 'S':
174                    start.x = now.x = x;
175                    start.y = now.y = y;
176                    break;
177            }
178        }
179    }
180 
181    //
182    // 経路探索
183    // 上下左右に対して再帰的に検索をかける
184    //
185    SearchPath(0, start, start, dat, width, start, goal);
186 
187    //探索したパスを元に最短経路を描画する
188    FindPath(&sl, goal, start, goal, dat, width);
189 
190    //
191    //デバグ用表示
192    //
193    for(uint y=0; y<sl.size(); ++y){
194        cout << sl[y] << endl;
195    }
196 
197    //
198    //ファイル書き出し
199    //
200    ofstream ofs("out.txt");
201    for(uint y=0; y<sl.size(); ++y){
202        ofs << sl[y] << endl;
203    }
204    ofs.close();
205 
206    //あとしまつ
207    delete [] dat;
208    dat = 0;
209 
210    return 0;
211}
結果は惨敗。相手は１時間ちょっとで終わっていたのに対して、私は４時間かけてようやくといったところ。先生はPythonを使われていいたようです。てかこの手の問題でC++を使う時点でダメだろ俺…。Pythonなどの高級言語や、関数型言語ならもっともっと美しく簡潔に書けたでしょうね。とにかく自分の無能さが身に染みてわかった。くやしい！

自分のアホさにげんなりした問題でした。さて、寝よう(：Ｄ)┼─┤
投稿者 washi 時刻: 3:43
ラベル: ,

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)