最短経路のアルゴリズム

質問

このジャンルでお願いします。

左下の座標を(1,1)として
○(4,4)が△(7,2)に辿りつく最短経路のアルゴリズムが知りたいです。
■は通れない場所です。

□□□□□□□
□□■■□□□
□□□□■□□
□■□○■□□
□■□■■□□
□□■□□△□
□□□□□□□
↑
(1,1)

回答No.2

yaemon_2006 · ベストアンサー

#include <stdio.h>

typedef struct maze{
int map[9][9];
int steps;
} MAZE;

void Print(MAZE *maze)
{
char *marks[] = {"■", " ","・",};
int y, x;

for(y = 0; y < 9; y ++){
for(x = 0; x < 9; x ++){
printf("%s", marks[maze->map[y][x]]);
}
putchar('\n');
}
printf("Steps : %d\n\n", maze->steps);
return;
}

void Route(MAZE *maze, int *shortest, int y, int x)
{
if(y < 0 || 9 <= y) return;
if(x < 0 || 9 <= x) return;
if(maze->map[y][x] != 1) return;
if(maze->steps > *shortest) return;
maze->map[y][x] = 2;
if(y == 6 && x == 6){
Print(maze);
*shortest = maze->steps;
maze->map[y][x] = 1;
return;
}
maze->steps ++;
Route(maze, shortest, y, x + 1);
Route(maze, shortest, y + 1, x);
Route(maze, shortest, y, x - 1);
Route(maze, shortest, y - 1, x);
maze->map[y][x] = 1;
maze->steps --;
return;
}

int main(void)
{
MAZE maze = {
{{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 1, 1, 0, 0, 1, 1, 1, 0},
{0, 1, 1, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 1, 0, 0, 1, 1, 0},
{0, 1, 1, 0, 1, 1, 1, 1, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},},
0,
};
int shortest = 9 * 9;

Print(&maze);
Route(&maze, &shortest, 4, 4);
return 0;
}

お礼

ご返答ありがとうございます。
試してみましたが、これは凄いですね。ありがとうございます。

回答No.1

koko_u_

>○(4,4)が△(7,2)に辿りつく
「辿りつく」のに動けるのは上下左右だけ？斜めもOK？

単純に○の上下左右に 1 と書いて、1と書かれた升目の上下左右に 2 と書いて、2と書かれた升目の上下左右に 3 と書いて。。。を繰り返すとか？

あんま考えてないのでダメかも知らん。

お礼

ご返答ありがとうございます。
すいません、移動条件を書くのを忘れてました・・・
移動は上下左右だけです。