こんにちはー
今日はチョコを探しに、
献血してきました。
チョコは貰えなかったけど、アクエリアスは貰えて、血も減ってとても気分が良くなりました。佐々木です。
東京に来て、まだ2回しか献血してなかったんだね。
とりあえずスッキリした。
今回はですね、C言語での再帰による迷路の最短経路、最長経路の探索のプログラム
ってことで、なんか授業の課題とかで使えそうなやつを載っけます。
しかし、私のやり方以外にも、よりよい方法があると思いますので、評価を高く得たい場合は、さらに頑張ってください。
経路探索
｜例えば下図に示すように，通行可能なマス目に’0’が，障害物であって通行不能なマス目に’+’が記されている盤を考えましょう．
｜スタート地点をs，ゴール地点をgで指定して，最短経路及び最長経路を表示するプログラムを考えます。
｜ただし，同一の場所を2度以上通ってはならない．
今回はこの迷路を突破してみましょう！
パッと見、訳が分かりませんが、まぁいい。
考え方としては、
人間だったら問題ないけど、コンピュータさんはスタート地点を把握できてないので、
- スタート地点を教えてあげる
- とりあえず4方向に進んでみる
- 行き止まりだったら戻る
- 2,3を繰り返す
- ゴールに到着
- 2~5を繰り返し、最短経路・最長経路を探索
簡単ですね。
メイン関数は、迷路の準備と、探索する関数を作ってます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
int main(int argc, char* argv[]){//argc:引数の個数 argv:引数の文字列配列 char map[MAX][MAX];//要素 int width,height;//幅,高さ int i; /*迷路の準備*/ if(argc <= 1){//コマンドラインからの入力がない場合 width = 32; height = 32; strcpy(map[0], "++++++++++++++++++++++++++++++++"); strcpy(map[1], "s00000+00000000000+00000+000000+"); strcpy(map[2], "+++++0+0+++++++++0+++0+++0++++0+"); strcpy(map[3], "+000+000+0000000+000+0+000+0000+"); strcpy(map[4], "+0+0+++++0+++0+0+++0+0+0+0+++00+"); strcpy(map[5], "+0+000+000+000+00000+000+0+0000+"); strcpy(map[6], "+++0+0+++0+++++0+++++++++0+++00+"); strcpy(map[7], "+000+000+00000+000000000+0+0000+"); strcpy(map[8], "+0+0+++0+0+++++++++++++0+0+0+00+"); strcpy(map[9], "+0+0+0+0+0000000000000+0+0+0+00+"); strcpy(map[10],"+0+0+0+0+++0+++++++++0+0+0+0++++"); strcpy(map[11],"+0+0+000+0000+000000+0+000+0000+"); strcpy(map[12],"+++0+0+++0+++++++0+++0+++++0+00+"); strcpy(map[13],"+000+00000+000000000+0+000+0+00+"); strcpy(map[14],"+0+0+++++++0+++++0+++0+0+0+0++++"); strcpy(map[15],"+0+0+00000+0+000+000+0+0+0+00+0+"); strcpy(map[16],"+++0+0+++++0+++0+0+++0+0+0+0000+"); strcpy(map[17],"+000+00000000000+000+000+000+00+"); strcpy(map[18],"+0+0+++++++++++0+0++++++++++++++"); strcpy(map[19],"+0+0+00000+000+0+000000000+0000+"); strcpy(map[20],"+0+0+0+0+0+0+0+++0+++++0+++0++++"); strcpy(map[21],"+0+000+0+0+0+000000000+00000+00+"); strcpy(map[22],"+0+++++0+++0+0+0+++0+++++++++00+"); strcpy(map[23],"+0+000+00000+0+0+00000000000000+"); strcpy(map[24],"+0+++0+++++++++0++++++++++0+++++"); strcpy(map[25],"+000+00000+00000+00000+00000000+"); strcpy(map[26],"+++0+++0+++0+++++0+++0+0+++++00+"); strcpy(map[27],"+0+0000000+000000000+0+0+000000+"); strcpy(map[28],"+0+++0+++++0+++++++0+0+++00+++0+"); strcpy(map[29],"+0+000+000+000+000+0+00000000+0+"); strcpy(map[30],"+000+000+0+000+0+0+0+000+00+0+0g"); strcpy(map[31],"++++++++++++++++++++++++++++++++"); }else{//コマンドラインからの入力がある場合 //入力が正しいという前提 height = argc-1; width = strlen(argv[1]); for(i=0; i<height; i++){ strcpy(map[i],argv[i+1]); } } //経路探索関数 findRoute(width,height,map); return 0; } |
このfindRoute内で再帰(loop)を使って、迷路を突破する感じですね。
make_boardでは、4方向進んだときに、障壁+の外側に行かないように、さらに+で囲っています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
//経路探索関数 void findRoute(int width, int height, char map[][MAX]){ //width:幅 height:高さ map[MAX]:要素 int x,y,i; int starty, startx, goaly, goalx; int board[MAX][MAX]; int route[MAX][MAX]; //縁付き迷路盤の作成 make_board(width, height, &starty, &startx, &goaly, &goalx, map, board); //縁の分だけサイズ拡張 width+=2*EDGE; height+=2*EDGE; //迷路を経路表示用配列にコピー matrix_copy(width, height, board, route); //スタート地点の検索 for(y=0;y<EDGE+height;y++){ for(x=0;x<EDGE+width;x++){ if(map[y-EDGE][x-EDGE] == 's') route[starty][startx]=1; //スタート地点の距離を1にする } } y=starty; //スタート地点(y)の確保 x=startx; //スタート地点(x)の確保 route[y][x]=1; //routeに距離1 cnt=1; //カウントを1 //再帰で経路探索 loop(width, height, y, x, map, route, goaly, goalx); //経路の表示 route_print(width, height, route); } |
そして、
一番重要な再帰の部分は
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//再帰で経路探索 void loop(int width, int height, int y, int x, char map[][MAX], int route[][MAX], int goaly, int goalx){ int i,keepy,keepx; for(i=0;i<4;i++){ if(route[y+dy[i]][x+dx[i]]==0){ //未踏の地だったら route[y+dy[i]][x+dx[i]]=++cnt; //(スタート地点からの距離+1)を記録 y=y+dy[i]; x=x+dx[i]; //場所を移動 keepy=dy[i]; keepx=dx[i]; //場所覚えとく if(y==goaly && x==goalx){ //goalであったら if(138>cnt){ //最短だったら printf("/ MIN /\n"); route_print(width, height, route); //最短経路の表示 } if(237<cnt){ //最長だったら printf(" / MAX /\n"); route_print(width, height, route); //最長経路の表示 exit(1); } } else{ //goalじゃなかったら loop(width, height, y, x, map, route, goaly, goalx); //loopを繰り返す } //loopしたけど、 route[y][x]=0; //進む先がなかったということで、場所を戻す y=y-keepy; x=x-keepx; //前の座標 cnt--; //距離も-1 } } } |
となります。
ただ、最短最長をアナログチックに判定してます。分からなくて。
頑張れば、最短最長を自動的に検出できると思いますので、頑張ってください。
結果
最短
最長
最後に全体のコードを載せておきます
そのうちにもっと分かり易く書き直したいと思います。
コードを説明するって難しい。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 |
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 50 #define EDGE 1 #define WALL -1 //探索方向指定用配列 static int dx[4]={0,1,0,-1}; static int dy[4]={-1,0,1,0}; static int cnt,cntmin,cntmax; static int min,max; /*ボードの作成*/ void make_board(int width, int height, int *starty, int *startx, int *goaly, int *goalx, char map[][MAX], int board[][MAX]){ int x,y; for(y=0;y<EDGE;y++){ for(x=0;x<width+2*EDGE;x++){ board[y][x]=WALL;//上縁を付ける } } for(;y<EDGE+height;y++){ for(x=0;x<EDGE;x++){ board[y][x]=WALL;//左縁を付ける } for(;x<EDGE+width;x++){ switch(map[y-EDGE][x-EDGE]){ case '+'://壁 board[y][x]=WALL; break; case 's'://スタート地点の検出 *starty=y; *startx=x; break; case 'g'://ゴール地点の検出 *goaly=y; *goalx=x; break; default://通路 board[y][x]=0; } } for(;x<EDGE+width+EDGE;x++){ board[y][x]=WALL;//右縁を付ける } } for(;y<EDGE+height+EDGE;y++){ for(x=0;x<EDGE+width+EDGE;x++){ board[y][x]=WALL;//下縁を付ける } } } /*配列のコピー*/ void matrix_copy(int xsize, int ysize, int matrix1[][MAX], int matrix2[][MAX]){ int x,y; for(y=0;y<ysize;y++) for(x=0;x<xsize;x++) matrix2[y][x]=matrix1[y][x]; } /*経路の表示*/ void route_print(int xsize, int ysize, int board[][MAX]){ int x,y; for(y=0; y<ysize; y++){ for(x=0; x<xsize; x++){ if(board[y][x]==WALL) printf(" +"); else if(board[y][x]==0) printf(" 0"); else printf("%4d", board[y][x]); } printf("\n"); } printf("\n"); } //再帰で経路探索 void loop(int width, int height, int y, int x, char map[][MAX], int route[][MAX], int goaly, int goalx){ int i,keepy,keepx; for(i=0;i<4;i++){ if(route[y+dy[i]][x+dx[i]]==0){ //未踏の地だったら route[y+dy[i]][x+dx[i]]=++cnt; //(スタート地点からの距離+1)を記録 y=y+dy[i]; x=x+dx[i]; //駒を移動 keepy=dy[i]; keepx=dx[i]; if(y==goaly && x==goalx){ if(138>cnt){ printf("/ MIN /\n"); route_print(width, height, route); //経路の表示 } if(237<cnt){ printf(" / MAX /\n"); route_print(width, height, route); //経路の表示 exit(1); } } else{ loop(width, height, y, x, map, route, goaly, goalx); } route[y][x]=0; //進む先がないので、戻す y=y-keepy; x=x-keepx; //どう進んだかを覚える cnt--; } } } //経路探索関数 void findRoute(int width, int height, char map[][MAX]){ //width:幅 height:高さ map[MAX]:要素 int x,y,i; int starty, startx, goaly, goalx; int board[MAX][MAX]; int route[MAX][MAX]; //縁付き迷路盤の作成 make_board(width, height, &starty, &startx, &goaly, &goalx, map, board); //縁の分だけサイズ拡張 width+=2*EDGE; height+=2*EDGE; //迷路を経路表示用配列にコピー matrix_copy(width, height, board, route); //経路の表示 //route_print(width, height, route); printf("\n\n"); for(y=0;y<EDGE+height;y++){ for(x=0;x<EDGE+width;x++){ if(map[y-EDGE][x-EDGE] == 's') route[starty][startx]=1; //スタート地点の距離を1にする } } y=starty; x=startx; route[y][x]=1; cnt=1; min=0; max=0; //再帰で経路探索 loop(width, height, y, x, map, route, goaly, goalx); //経路の表示 route_print(width, height, route); } int main(int argc, char* argv[]){//argc:引数の個数 argv:引数の文字列配列 char map[MAX][MAX];//要素 int width,height;//幅,高さ int i; if(argc <= 1){//コマンドラインからの入力がない場合 width = 32; height = 32; strcpy(map[0], "++++++++++++++++++++++++++++++++"); strcpy(map[1], "s00000+00000000000+00000+000000+"); strcpy(map[2], "+++++0+0+++++++++0+++0+++0++++0+"); strcpy(map[3], "+000+000+0000000+000+0+000+0000+"); strcpy(map[4], "+0+0+++++0+++0+0+++0+0+0+0+++00+"); strcpy(map[5], "+0+000+000+000+00000+000+0+0000+"); strcpy(map[6], "+++0+0+++0+++++0+++++++++0+++00+"); strcpy(map[7], "+000+000+00000+000000000+0+0000+"); strcpy(map[8], "+0+0+++0+0+++++++++++++0+0+0+00+"); strcpy(map[9], "+0+0+0+0+0000000000000+0+0+0+00+"); strcpy(map[10],"+0+0+0+0+++0+++++++++0+0+0+0++++"); strcpy(map[11],"+0+0+000+0000+000000+0+000+0000+"); strcpy(map[12],"+++0+0+++0+++++++0+++0+++++0+00+"); strcpy(map[13],"+000+00000+000000000+0+000+0+00+"); strcpy(map[14],"+0+0+++++++0+++++0+++0+0+0+0++++"); strcpy(map[15],"+0+0+00000+0+000+000+0+0+0+00+0+"); strcpy(map[16],"+++0+0+++++0+++0+0+++0+0+0+0000+"); strcpy(map[17],"+000+00000000000+000+000+000+00+"); strcpy(map[18],"+0+0+++++++++++0+0++++++++++++++"); strcpy(map[19],"+0+0+00000+000+0+000000000+0000+"); strcpy(map[20],"+0+0+0+0+0+0+0+++0+++++0+++0++++"); strcpy(map[21],"+0+000+0+0+0+000000000+00000+00+"); strcpy(map[22],"+0+++++0+++0+0+0+++0+++++++++00+"); strcpy(map[23],"+0+000+00000+0+0+00000000000000+"); strcpy(map[24],"+0+++0+++++++++0++++++++++0+++++"); strcpy(map[25],"+000+00000+00000+00000+00000000+"); strcpy(map[26],"+++0+++0+++0+++++0+++0+0+++++00+"); strcpy(map[27],"+0+0000000+000000000+0+0+000000+"); strcpy(map[28],"+0+++0+++++0+++++++0+0+++00+++0+"); strcpy(map[29],"+0+000+000+000+000+0+00000000+0+"); strcpy(map[30],"+000+000+0+000+0+0+0+000+00+0+0g"); strcpy(map[31],"++++++++++++++++++++++++++++++++"); }else{//コマンドラインからの入力がある場合 //入力が正しいという前提 height = argc-1; width = strlen(argv[1]); for(i=0; i<height; i++){ strcpy(map[i],argv[i+1]); } } //経路探索関数 findRoute(width,height,map); return 0; } |
Comment On Facebook