- ベストアンサー
最短経路のアルゴリズム
このジャンルでお願いします。 左下の座標を(1,1)として ○(4,4)が△(7,2)に辿りつく最短経路のアルゴリズムが知りたいです。 ■は通れない場所です。 □□□□□□□ □□■■□□□ □□□□■□□ □■□○■□□ □■□■■□□ □□■□□△□ □□□□□□□ ↑ (1,1)
- takagoo100
- お礼率85% (739/868)
- C・C++・C#
- 回答数2
- ありがとう数2
- みんなの回答 (2)
- 専門家の回答
質問者が選んだベストアンサー
#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; }
その他の回答 (1)
- koko_u_
- ベストアンサー率18% (459/2509)
>○(4,4)が△(7,2)に辿りつく 「辿りつく」のに動けるのは上下左右だけ?斜めもOK? 単純に○の上下左右に 1 と書いて、1と書かれた升目の上下左右に 2 と書いて、2と書かれた升目の上下左右に 3 と書いて。。。を繰り返すとか? あんま考えてないのでダメかも知らん。
お礼
ご返答ありがとうございます。 すいません、移動条件を書くのを忘れてました・・・ 移動は上下左右だけです。
関連するQ&A
- 最短経路問題のアルゴリズム
最短経路問題のアルゴリズムにはどのようなものがありますか? ダイクストラくらいしか知りません。教えてください。 カテゴリー違いだったら書き直します。
- ベストアンサー
- 数学・算数
- 最短経路を計算するプログラム
下の図のようなものを用いて、スタート(S)からゴール(G)までいく最短経路を計算するプログラムをVisual Studio 2005のC++で作ったアルゴリズムが知りたいです。
- 締切済み
- C・C++・C#
- ベルマンフォードのアルゴリズム
このカテゴリーであってる・・・かな・・。 とりあえず、ネットワークのアルゴリズムなので。 最短経路を求めるアルゴリズムは、 ダイクストラしか知らなかったのですが、 ベルマンフォードというアルゴリズムがあると知りました。 どのようなアルゴリズムなのでしょうか? ダイクストラと比較してどうなのでしょうか?
- ベストアンサー
- その他(インターネット接続・通信)
- 最短経路について
正方形を横に5個、縦に4個ならべた碁盤を考える(つまり線の上を通る) このとき左下にA地点、右上にB地点を置き、A地点から2つ右上の(つまりA地点から右に2つ、上に2つ行くと到達する)地点にP地点を置くとする (1)P地点が右左折禁止(つまり通過するときは直進することしかできない)の場合、A地点からB地点まで行く最短経路は全部で何通りあるか 答えには左から右へP地点を直進する場合と下から上へP地点を直進する場合に分けて、前者は3C1×4C2、後者は3C1×4C1通りでそれらとP地点が通行止めのときのA地点からB地点までの最短経路の全体を足しているのですが3C1×4C2と3C1×4C1がどういう意味か分かりません 教えてください
- ベストアンサー
- 数学・算数
- 最短経路を教えてください!
大阪全日空ホテルからJR難波まで行きたいのですが、最短経路を教えてください。JR以外を使ったことがないので、環状線で行こうかと思いましたが時間が微妙なので、より早くつく経路を探しています。 あと、利用するのが金曜の夕方5時半ぐらいなのですが、帰宅ラッシュとかぶったりするのでしょうか?? 詳しく教えていただくとありがたいです!よろしくお願いします!!
- 締切済み
- その他(国内旅行・情報)
- 任意の2地点間の全経路探索について
ネットワーク上においてダイクストラ法を使うと任意の2地点間の最短経路が求められますが、最短経路だけでなく最長経路など任意の2地点間における全ての経路を求めたいと考えていますが、なかなか良いアルゴリズムができません。詳しい方御教授お願いいたします。
- 締切済み
- 数学・算数
- 名古屋-大阪間最短経路について
名古屋ー大阪の高速を使わない最短経路はどのルートなんでしょうか? 時間的に最短経路です 1号でもなく25号でもなく、県道を使うと最短と聞いたこともありますが、どの道がご存知でしょうか?
- ベストアンサー
- その他(車・バイク・自転車)
お礼
ご返答ありがとうございます。 試してみましたが、これは凄いですね。ありがとうございます。