【WRM007】Aquilaのソースコード
アルゴリズム部分だけです。
個人的には探索アルゴリズムに関しては他のどのチームにも劣らなかったと思っています。
(異論は認めます.)
ソースコード
Aquila-2019/Src/source at master · rakuseirobot/Aquila-2019 · GitHub
↑ ここの data_structure.hpp & .cpp 、core.hpp & .cpp 、 iris.hpp & .cpp にあります。
・iris.hpp & .cpp以外は単体で動作します。(テスト済み)
・実際の迷路探索はiris.cpp内の_h_stack_dfs();で動作します。
・ご自由にお使いください。
・わからないことがあればEmileに連絡お願いします。(Twitter等で.)
・多分バグが残ってます。
プログラムの設計スタイルについて
data_structureでデータ構造を定義して、coreでそれらを一つに管理しています。
そして、irisでI/Oを管理しています。
Mappingは重み無し無向グラフ (by自己参照構造体)で、nodeという名前です.(data_structureの中です)
そのnode内にAVLtreeを絡めてます.
関数の仕様について
マッピング用の自己参照構造体及び付随する関数
struct node{ uint8_t x=100,y=100,z=10;//coordinate uint8_t flag,type;//for bfs, search uint8_t color;//for 'real' bfs uint8_t depth=255,dist=255;// bl ac=false;//already checked? node* next[4]={np}; // 4neighborhood node* back=np; //backtrack (unused) node* child[2]={np,np};//AVLtree uint8_t height=0; //AVLtree };
typeはそのマスのタイプです。
例えば、被災者(熱源)がいる、黒タイル、何もない、等..
それらを以下のようなクラスに一括で管理しています。
class core{ node* now; node* start;//it may be unnecessary.But now, it is used in dfs. int dir;//0::<,1::^,2::>,3::v //for status node* ans;//dfs's answer. int flg;//0 or 1 //for dfs queue q;//for bfs node* pre;//一つ前の頂点 public: bool blk_tile; AVLtree at;//avltree nodes mall;//newの代わり stack stk;//改造stack node* start_f[20];//間に合わず core(); void turn_r();//map上で右回転 void turn_l();//map上で左回転 void w_now(node* u);//現在地書き込み int r_flg();//現在のflgの取得(map内の探索flg) node* r_now();//現在地取得 node* r_start();//スタート地点取得 node* r_pre();//移動前のnodeの取得 void dfs(node* t,int x,int y,int z,int depth);//map内DFS(内部実装) node* find(int x,int y,int z);//map内探索クエリ void ins_node(node* x);//AVLtreeに挿入 void cn_graph(node* v, node* u);//(node)vとuを接続 void cn_tree(node* par,node* v);//node->backに関して接続 void ap_node(node* t,int dire);//頂点追加クエリ node* ac_next(node* t,int now_dir,int dire,int dist);//頂点取得クエリ(内部) node* ac_next(int dire,int dist);//頂点取得クエリ bl ck_conect(node* s,node* t);//接続確認クエリ void go_st();//map内前進 void cl_dist(node* t,int d);//頂点に書き込まれた距離のクリア(内部) void clear_dist();//頂点に書き込まれた距離のクリア void bfs(node* s,node* t);//map内bfs(距離算出用) /*ここからはDPの実装*/ bool hamilton;//trueならans_vとvertex_size見て,最適化 bool now_hami;//いま最適化されてるか? stack ans_v;//最適化された頂点集合 node* vertex[M_V_SIZE+2];//vertexs int8_t vertex_size; //v[i]->v[i-1]->...(i=|v|,|v|-1,,1,0) uint8_t dist[M_V_SIZE+2][M_V_SIZE+2]; //dist[s][t]:=distance(s->t) uint16_t dp[1<<(M_V_SIZE+2)][M_V_SIZE+2];//memo化 //集合(set)のiで終わる最短ハミルトン路の長さを算出 //ただし、始点v[0]と終点v[vertex_size]は固定 //dp[(set)][i] :=ans(dp_calc) int8_t prev[1<<(M_V_SIZE+2)][M_V_SIZE+2];//backtrack //prev[(set)][i]:~dp[(Set)][i]の解をとる時の,前の頂点 node* vertex_calc(int set,int i,int v_size);//内部実装 bool dp_init();//頂点集合初期化及び最適化条件に合致するか判定 bool dp_calc();//最適化 };
