迷宫问题
用以下的程序求出迷宫的最短路径，最多到13*13的迷宫可执行，往上就光标挺那半天不动，请各位高手救命，马上就要交了！
小妹这厢有礼了，万分感谢！！
#include <stdio.h>
#include "iostream.h"
#define NUMROWS 13
#define NUMCOLS 13
#define INFINITY 999999
//int read_maze(char [][], int *, int *);
//void display_maze(char [][]);
//void copy_maze(char [][], char[][]);
//void solve_maze(char [][], int, int, int);
char mazeBest[NUMROWS][NUMCOLS]; /* Stores best maze found so far. */
int lengthBest = INFINITY; /* Stores length of best maze found so far. */
/*
* Read maze from "maze.txt".
* Fill in *sRow and *sCol with position of 'O'.
* If error, return 0, else return 1.
*/
int read_maze(char maze[NUMROWS][NUMCOLS], int *sRow, int *sCol)
{
FILE *fpMaze;
int row, col;
/* Open maze text file, make sure it opens OK. */
if ((fpMaze = fopen("m.txt", "r")) == NULL)
return 0;
/* Loop through the rows. */
for (row = 0; row < NUMROWS; row++)
{
/* Loop through the column in current row. */
for (col = 0; col < NUMROWS; col++)
{
maze[row][col] = getc(fpMaze);
/* Check if this is the starting position. */
if (maze[row][col] == 'O')
{
*sRow = row;
*sCol = col;
}
}
/* Ignore newline at end of each row. */
getc(fpMaze);
}
return 1;
}
/* Display the maze passed as a parameter to standard output. */
void display_maze(char maze[NUMROWS][NUMCOLS])
{
int row, col;
for (row = 0; row < NUMROWS; row++)
{
for (col = 0; col < NUMCOLS; col++)
{
putchar(maze[row][col]);
}
putchar('\n');
}
return;
}
/* Copy the maze in mazeSrc to mazeDest. */
void copy_maze(char mazeSrc[NUMROWS][NUMCOLS],
char mazeDest[NUMROWS][NUMCOLS])
{
int row, col;
for (row = 0; row < NUMROWS; row++)
{
for (col = 0; col < NUMCOLS; col++)
{
mazeDest[row][col] = mazeSrc[row][col];
}
}
return;
}
/*
* Given:
* (1) maze with path so far
* (2) current row
* (3) current column
* (4) length of path so far
* The function solve_maze recursively tries to solve the maze.
*
* When a solution is found, compare it to previous best found solution,
* and update appropriate globals if necessary.
*/
int solve_maze(char mazeCur[NUMROWS][NUMCOLS], int curRow, int curCol, int length)
{
/* If already as long as best solution, no need to look further. */
if (length >= lengthBest)
return 0;
/* Check if solution found. */
if ((mazeCur[curRow-1][curCol] == 'X') ||
(mazeCur[curRow+1][curCol] == 'X') ||
(mazeCur[curRow][curCol+1] == 'X') ||
(mazeCur[curRow][curCol-1] == 'X') ||
(mazeCur[curRow-1][curCol-1]== 'X') ||
(mazeCur[curRow-1][curCol+1]=='X')||
(mazeCur[curRow+1][curCol-1]=='X')||
(mazeCur[curRow+1][curCol+1]=='X'))
{
/* Found solution, better then previous best, update globals. */
lengthBest = length;
copy_maze(mazeCur, mazeBest);
return 0;
}
/* Recurse in each possible direction that is empty. */
if (mazeCur[curRow-1][curCol] == ' ')
{
mazeCur[curRow-1][curCol] = 'O';
solve_maze(mazeCur, curRow-1, curCol, length+1);
mazeCur[curRow-1][curCol] = ' ';
}
if (mazeCur[curRow+1][curCol] == ' ')
{
mazeCur[curRow+1][curCol] = 'O';
solve_maze(mazeCur, curRow+1, curCol, length+1);
mazeCur[curRow+1][curCol] = ' ';
}
if (mazeCur[curRow][curCol-1] == ' ')
{
mazeCur[curRow][curCol-1] = 'O';
solve_maze(mazeCur, curRow, curCol-1, length+1);
mazeCur[curRow][curCol-1] = ' ';
}
if (mazeCur[curRow][curCol+1] == ' ')
{
mazeCur[curRow][curCol+1] = 'O';
solve_maze(mazeCur, curRow, curCol+1, length+1);
mazeCur[curRow][curCol+1] = ' ';
}
if (mazeCur[curRow-1][curCol-1]== ' ')
{mazeCur[curRow-1][curCol-1] = 'O';
solve_maze(mazeCur, curRow-1, curCol-1, length+1);
mazeCur[curRow-1][curCol-1] = ' ';
}
if (mazeCur[curRow-1][curCol+1]== ' ')
{mazeCur[curRow-1][curCol+1] = 'O';
solve_maze(mazeCur, curRow-1, curCol+1, length+1);
mazeCur[curRow-1][curCol+1] = ' ';
}
if (mazeCur[curRow+1][curCol+1]== ' ')
{mazeCur[curRow+1][curCol+1] = 'O';
solve_maze(mazeCur, curRow+1, curCol+1, length+1);
mazeCur[curRow+1][curCol+1] = ' ';
}
if (mazeCur[curRow+1][curCol-1]== ' ')
{mazeCur[curRow+1][curCol-1] = 'O';
solve_maze(mazeCur, curRow+1, curCol-1, length+1);
mazeCur[curRow+1][curCol-1] = ' ';
}
return lengthBest;
}
int main(void)
{
char maze[NUMROWS][NUMCOLS]; /* Stores maze read from input file. */
int startRow, startCol; /* Starting point in maze. */
if (read_maze(maze, &startRow, &startCol) == 0)
{
printf("Error reading maze from file maze.txt!\n");
return 0;
}
//printf("Starting maze:\n");
//display_maze(maze);
solve_maze(maze, startRow, startCol, 0);
if (lengthBest == INFINITY)
{
printf("\nNo path to goal was found in maze!\n");
return 0;
}
else
{
printf("\nBest solution found:\n");
display_maze(mazeBest);
}
cout<<"total num of steps used are:"<<lengthBest+1;
return 0;
}
问题点数：100、回复次数：19Top
1 楼rtdb（东临碣石）回复于 2003-02-04 14:05:12 得分 0
#define NUMROWS 13
#define NUMCOLS 13
你的程序中最多就支持13*13，
再多就数组越界了。
看来不是你自己写的。
想要多少就改上面两行吧。
Top
2 楼leaf3191（今晚不加班~~~）回复于 2003-02-04 14:41:56 得分 0
你这个问题也太简单了吧！
就把源程序给出来，问题也没有，叫人怎么看Top
3 楼Frank001（Frank）回复于 2003-02-04 14:46:24 得分 0
我猜想这个程序不是你写的。
你要把问题说清楚，大家才好帮你啊Top
4 楼pcdingding（）回复于 2003-02-04 15:04:16 得分 0
"你的程序中最多就支持13*13，
再多就数组越界了。
看来不是你自己写的。
想要多少就改上面两行吧。"
哎，这么简单就不问你了，我的意思就是若define到20，就不执行了。
我的问题就是帮我看看程序有没有问题。
为什么说不是我写的？~
有现成的算法啊，只是变成代码啊！
原谅我比较菜，好心人帮我看看吧。多谢！
Top
5 楼lonelybug（孤独虫子）回复于 2003-02-04 15:24:31 得分 0
这个再那个编译器下可以测试呀！？用visual studio.net可以吗！？Top
6 楼zhy0（zero）回复于 2003-02-04 17:26:15 得分 10
程序应该是正确的。递归方法在简化程序设计的同时降低了程序运行效率。大量的递归调用很可能导致堆栈溢出，或者由于运算量太大需要很长的时间来运行。define到20大概就是这种情况。不知道这个程序有什么要求，一定要用到13以上的情况建议你换种算法。ps:你这个迷宫好另类，不但可以左右上下移动还可以斜着走。Top
7 楼pcdingding（）回复于 2003-02-05 00:20:54 得分 0
visual studio.net应该可以把。
那介绍个效率高的算法给我吧，我们就要求的是20*20的（有源码最好了~。急，急！马上就要交差了）多谢先！Top
8 楼cupidvenus（小鱼儿）回复于 2003-02-05 09:00:25 得分 0
你把
#define NUMROWS 13
#define NUMCOLS 13
两行改成
#define NUMROWS 20
#define NUMCOLS 20
不就行了吗？Top
9 楼pcdingding（）回复于 2003-02-05 10:21:47 得分 0
我不是说了define到20，计算机半天没动静了吗？Top
10 楼idler（告别teenage)(偶是豆子。。。)(歇业休息。。。）回复于 2003-02-05 10:24:26 得分 0
最好把题目完整地贴出来。
用Dijkstra啊，我看看先。Top
11 楼idler（告别teenage)(偶是豆子。。。)(歇业休息。。。）回复于 2003-02-05 10:32:11 得分 0
输入文件格式？（'O'入口、'X'出口、' '路径？）
Top
12 楼idler（告别teenage)(偶是豆子。。。)(歇业休息。。。）回复于 2003-02-05 10:37:50 得分 0
没有必要把整个迷宫传递给下一层，又不是多线程。Top
13 楼willhuang78（）回复于 2003-02-05 10:44:21 得分 0
数组开的太小了Top
14 楼pcdingding（）回复于 2003-02-06 03:28:16 得分 0
题目就是20*20的区域，找从（0，0）到（20，20）的最短路径。
对“X”是出口，“O”是入口，“ ”是可走的路，枪我是用“*”的
那以上程序的可以帮我改吗？
或另写一个？
非常，非常感谢！Top
15 楼dcyu（Dd）回复于 2003-02-06 11:11:07 得分 0
http://vip.6to23.com/dcyu/works/ds.zipTop
16 楼idler（告别teenage)(偶是豆子。。。)(歇业休息。。。）回复于 2003-02-06 16:15:08 得分 90
写了一个，思路一样的，没有测试过。结果在g_result里。
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 32767
#define MAZE_SIZE_ROW 20
#define MAZE_SIZE_COL 20
#define MAZE_FILENAME "maze.txt"
#define MAZE_WALL '*'
#define MAZE_FREE ' '
#define MAZE_START 'O'
#define MAZE_END 'X'
#define MAZE_PATH '.'
#define VALID_POS(row, col) ((row > 0) && (row < MAZE_SIZE_ROW) && \
(col > 0) && (col < MAZE_SIZE_COL))
struct maze_t
{
char maze[MAZE_SIZE_ROW][MAZE_SIZE_COL];
};
struct pos_t
{
int row, col;
};
const unsigned char g_dir[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
{1, 0}, {1, -1}, {0, -1}, {-1, -1}};
struct maze_t g_maze, g_result;
struct pos_t start;
// struct pos_t end;
int g_min_length = INFINITY;
int g_cur_length = 0;
void copy_maze(struct maze_t * dest, const struct maze_t * src)
{
memcpy(dest, src, sizeof(struct maze_t));
}
void read_maze()
{
int row, col;
FILE * fin;
if ((fin = fopen(MAZE_FILENAME, "r")) == NULL)
{
exit(-1);
}
for (row = 0; row < MAZE_SIZE_ROW; row++)
{
for (col = 0; col < MAZE_SIZE_COL; col++)
{
g_maze.maze[row][col] = (char)getc(fin);
if (g_maze.maze[row][col] == MAZE_START)
{
start.row = row;
start.col = col;
}
// else
// {
// if (g_maze.maze[row][col] == MAZE_END)
// {
// end.row = row;
// end.col = col;
// }
// }
}
getc(fin);
}
}
void search_maze(struct pos_t cur_pos)
{
int i;
struct pos_t next_pos;
if (VALID_POS(cur_pos.row, cur_pos.col))
{
if (g_maze.maze[cur_pos.row][cur_pos.col] == MAZE_END)
{
if (g_cur_length < g_min_length)
{
g_min_length = g_cur_length;
copy_maze(&g_result, &g_maze);
}
return;
}
g_maze.maze[cur_pos.row][cur_pos.col] = MAZE_PATH;
g_cur_length++;
for (i = 0; i < 8; i++)
{
next_pos.row = cur_pos.row + g_dir[i][0];
next_pos.col = cur_pos.col + g_dir[i][1];
if (g_maze.maze[next_pos.row][next_pos.col] == MAZE_FREE)
{
search_maze(next_pos);
}
}
g_cur_length--;
g_maze.maze[cur_pos.row][cur_pos.col] = MAZE_FREE;
}
}
int main()
{
read_maze();
search_maze(start);
return 0;
}
Top
17 楼idler（告别teenage)(偶是豆子。。。)(歇业休息。。。）回复于 2003-02-06 16:16:02 得分 0
忘了fclose(fin)了。:-STop
18 楼idler（告别teenage)(偶是豆子。。。)(歇业休息。。。）回复于 2003-02-06 20:12:44 得分 0
其实这个问题应该用BFS做。Top
19 楼pcdingding（）回复于 2003-02-21 12:43:44 得分 0
Thank you very much!sorry to reply late.Top
