迷路を解くプログラムについて
迷路を脱出する経路を探索するプログラムを作成したいのですが、
何をすればいいのかまったくわかりません
以下のプログラムはあるんですが、このプログラムを改良していくということなんでしょうか？左上からスタートして右下がゴールらしいのですがやり方教えてください
#include <stdlib.h>
#include <stdio.h>
#include "List.h"
#define LEN 256
int maze[LEN][LEN];
void readMaze(char* filename, int *w, int *h, int maze[LEN][LEN]) {
FILE *fp;
int x, y;
if (0 != fopen_s(&fp, filename, "r")) {
fprintf(stderr, "指定された迷路の入力ファイルを開くことができませんでした．\n");
exit(-1);
}
fscanf_s(fp, "%d,%d\n", w, h);
for (y = 0; y < 2 * *h + 1; y++) {
for (x = 0; x < 2 * *w + 1; x++) {
fscanf_s(fp, "%d%*[^-0-9]", &(maze[y][x]));
}
}
fclose(fp);
}
void writeMaze(char* filename, int w, int h, int maze[LEN][LEN]) {
FILE *fp;
int x, y;
if (0 != fopen_s(&fp, filename, "w")) {
fprintf(stderr, "指定された迷路の出力ファイルを開くことができませんでした．\n");
exit(-1);
}
fprintf_s(fp, "%d,%d\n", w, h);
for (y = 0; y < 2 * h + 1; y++) {
for (x = 0; x < 2 * w + 1; x++) {
fprintf_s(fp, "%d", maze[y][x]);
if (x < 2 * w) {
fprintf_s(fp, ",");
}
else {
fprintf_s(fp, "\n");
}
}
}
fclose(fp);
}
// シンプルなバージョン：なるべく右下へ行けるなら右下へ
int main(int argc, char** argv) {
int w, h;
int x, y;
if (argc < 3) {
fprintf(stderr, "迷路の入出力ファイル名を指定してください．\n");
exit(-1);
}
// 迷路読込
readMaze(argv[1], &w, &h, maze);
// maze[1][1] から maze[2*h-1][2*w-1] までのルートを探す
x = 1; //座標の初期化
y = 1;
while (x != 2 * w - 1 || y != 2 * h - 1){
if (maze[y][x + 1] == 0) { // 右にまだ行ってない？
maze[y][x] = 1000;
x = x + 1;
}
else if (maze[y + 1][x] == 0) { // 下にまだ行ってない？
maze[y][x] = 1000;
y = y + 1;
}
else if (maze[y][x - 1] == 0) { // 左にまだ行ってない？
maze[y][x] = 1000;
x = x - 1;
}
else if (maze[y - 1][x] == 0) { // 上にまだ行ってない？
maze[y][x] = 1000;
y = y - 1;
}
else if (maze[y][x + 1] == 1000) { // 行き止まりなので右に引き返す
maze[y][x] = 1;
x = x + 1;
}
else if (maze[y + 1][x] == 1000) { // 行き止まりなので下に引き返す
maze[y][x] = 1;
y = y + 1;
}
else if (maze[y][x - 1] == 1000) { // 行き止まりなので左に引き返す
maze[y][x] = 1;
x = x - 1;
}
else if (maze[y - 1][x] == 1000) { // 行き止まりなので上に引き返す
maze[y][x] = 1;
y = y - 1;
}
}
maze[2 * h - 1][2 * w - 1] = 1000; // ゴール
// 答えを濃い色に
// 上記のプログラムはすでに答えを濃い色(1000)にしている
// 迷路書出
writeMaze(argv[2], w, h, maze);
return 0;
}
お礼
英語は苦手なので書いてある意味がわかるまで時間がかかるかもしれませんが、折角教えて頂いたのでチャレンジしてみたいと思います。どうもありがとうございました。