作成した経路を使ってスタートからゴールまでの最短経路を表示するプログラムを加えます。
まずは、結果配列を作りNONEでクリアします。
７．結果のクリア
関数名 ClearResult 戻り値 なし 引 数 結果 機 能 結果配列をNONEでクリアする |
void ClearResult(int result[ROW][COL])
{
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
result[i][j] = NONE;
}
}
}
|
main関数に結果配列resultとClearResult関数の呼び出しを追加します。
<sample program 157-01>
int main(void)
{
int maze[ROW][COL];
int path[ROW][COL];
int result[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
GenerateMaze(maze);
ShowMaze(maze);
ClearPath(path);
CheckPath(maze, path, START_X, START_Y, 1);
ShowPath(path);
ClearResult(result);
return 0;
}
|
<実行結果>
■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 -1 9 10 11 -1 13 -1 -1 -1 -1 4 -1 8 -1 -1 -1 12 -1 -1 7 6 5 6 7 8 9 10 11 -1 -1 8 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 7 8 9 10 11 -1 21 -1 -1 10 -1 8 -1 -1 -1 -1 -1 20 -1 -1 11 -1 9 -1 15 16 17 18 19 -1 -1 -1 -1 10 -1 14 -1 18 -1 20 -1 -1 13 12 11 12 13 -1 19 -1 21 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 続行するには何かキーを押してください・・・
８．結果のセット
関数名 SetResult 戻り値 なし 引 数 経路、結果 機 能 経路配列から正しい経路を結果配列に移す |
void SetResult(const int path[ROW][COL], int result[ROW][COL])
{
int x = GOAL_X;
int y = GOAL_Y;
int nowStep = path[y][x];
while (path[y][x] != 1) {
result[y][x] = nowStep;
if (path[y - 1][x] == nowStep - 1) {
y--;
}
else {
if (path[y][x + 1] == nowStep - 1) {
x++;
}
else {
if (path[y + 1][x] == nowStep - 1) {
y++;
}
else {
x--;
}
}
}
nowStep--;
}
result[y][x] = 1;
}
|
まずは、ゴールの歩数を取り出します。
そこから歩数が１小さいマスへ移動しつつ、結果配列に歩数を入れていきます。
これでスタートまでの最短経路が確定します。
※最短経路が複数ある場合は、その中の１つが選択されます。
<sample program 157-02>
int main(void)
{
int maze[ROW][COL];
int path[ROW][COL];
int result[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
GenerateMaze(maze);
ShowMaze(maze);
ClearPath(path);
CheckPath(maze, path, START_X, START_Y, 1);
ShowPath(path);
ClearResult(result);
SetResult(path, result);
return 0;
}
|
<実行結果>
■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 -1 9 10 11 -1 13 -1 -1 -1 -1 4 -1 8 -1 -1 -1 12 -1 -1 7 6 5 6 7 8 9 10 11 -1 -1 8 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 7 8 9 10 11 -1 21 -1 -1 10 -1 8 -1 -1 -1 -1 -1 20 -1 -1 11 -1 9 -1 15 16 17 18 19 -1 -1 -1 -1 10 -1 14 -1 18 -1 20 -1 -1 13 12 11 12 13 -1 19 -1 21 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 続行するには何かキーを押してください・・・
９．結果の表示
関数名 ShowResult 戻り値 なし 引 数 結果 機 能 最短経路を表示する |
void ShowResult(const int result[ROW][COL])
{
const char WALL[3] = "■";
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
if (result[i][j] == NONE) {
printf(WALL);
}
else {
printf("%2d", result[i][j]);
}
}
printf("\n");
}
printf("\n");
}
|
−１の個所は見づらいので、■を表示することにしました。
<sample program 157-03>
int main(void)
{
int maze[ROW][COL];
int path[ROW][COL];
int result[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
GenerateMaze(maze);
ShowMaze(maze);
ClearPath(path);
CheckPath(maze, path, START_X, START_Y, 1);
ShowPath(path);
ClearResult(result);
SetResult(path, result);
ShowResult(result);
return 0;
}
|
<実行結果>
■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 -1 9 10 11 -1 13 -1 -1 -1 -1 4 -1 8 -1 -1 -1 12 -1 -1 7 6 5 6 7 8 9 10 11 -1 -1 8 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 7 8 9 10 11 -1 21 -1 -1 10 -1 8 -1 -1 -1 -1 -1 20 -1 -1 11 -1 9 -1 15 16 17 18 19 -1 -1 -1 -1 10 -1 14 -1 18 -1 20 -1 -1 13 12 11 12 13 -1 19 -1 21 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ■■■■■■■■■■■ ■ 1 2 3■■■■■■■ ■■■ 4■■■■■■■ ■■■ 5■■■■■■■ ■■■ 6■■■■■■■ ■■■ 7■■■■■■■ ■■■ 8■■■■■■■ ■■■ 9■1516171819■ ■■■10■14■■■20■ ■■■111213■■■21■ ■■■■■■■■■■■ 続行するには何かキーを押してください・・・
完成しました！
↑の道が最短経路です。
ついでなので、さらに「おまけ」を作りましょう。