无锡市商品房发布平台:迷宫问题，最短路径

下面是用C写的程序：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define max_m 1000
#define max_n 1000

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int maze[max_m][max_n];
int m,n,start_row,start_col,end_row,end_col;
char c;

void read_maze()
{
int i,j;
char buf[256];
memset(buf, 0, sizeof(buf));
fgets(buf, 256, stdin);
sscanf(buf, "%d%d", &m, &n);
fgets(buf, 256, stdin);
sscanf(buf, "%d%d", &start_row, &start_col);
start_row--;start_col--;
fgets(buf, 256, stdin);
sscanf(buf, "%d%d", &end_row, &end_col);
end_row--;end_col--;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
scanf("%c", &c);
maze[i][j] = (c != '.');
}
fgets(buf, 256, stdin);
}
}

int new_value(int row, int col)
{
int i,new_row,new_col;
int result;
result = maze[row][col];
if (result == 0)
{
for (i = 0; i < 4; i++)
{
new_row = row + dir[i][0];
new_col = col + dir[i][1];
if (new_row >= 0 && new_row < m && new_col >= 0 && new_col < n && maze[new_row][new_col] < 0 && (result == 0 || maze[new_row][new_col] - 1 > result))
{
result = maze[new_row][new_col] - 1;
}
}
}
return result;
}

int find_shortest_path()
{
int changed,i,j,new_val,expect_val;
if (start_row < 0 || start_row >= m || start_col < 0 || start_col >= n || end_row < 0 || end_row >= m || end_col < 0 || end_col >= n || maze[start_row][start_col] != 0 || maze[end_row][end_col] != 0)
{
return 0;
}
changed = 1;
maze[end_row][end_col] = -1;
expect_val = -2;
while (changed && maze[start_row][start_col] == 0)
{
changed = 0;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
{
new_val = new_value(i,j);
if (new_val == expect_val && new_val != maze[i][j])
{
maze[i][j] = new_val;
changed = 1;
}
}
expect_val--;
}
return (maze[start_row][start_col] < 0);
}

void print_shortest_path()
{
int i,j,new_i,new_j,expect_val,k;
if (maze[start_row][start_col] >= 0)
{
printf("No path!\n");
return;
}
printf("%d %d\n", start_row+1, start_col+1);
i = start_row;
j = start_col;
for (expect_val = maze[start_row][start_col]+1; expect_val <= -1; expect_val++)
{
for (k = 0; k < 4; k++)
{
new_i = i + dir[k][0];
new_j = j + dir[k][1];
if (new_i >= 0 && new_i < m && new_j >= 0 && new_j < n && maze[new_i][new_j] == expect_val)
{
i = new_i;
j = new_j;
printf("%d %d\n", i+1,j+1);
break;
}
}
}
}

int main()
{
read_maze();
if (find_shortest_path())
{
print_shortest_path();
}
else
{
printf("No path!\n");
}
return 0;
}

程序运行示例：
7 8 //迷宫规格
1 1 //起点
7 8 //终点
.###....
...##.#.
##....#.
...##...
.#..#.#.
...#...#
##...#.. //迷宫样子 未加边框
1 1
2 1
2 2
2 3
3 3
3 4
3 5
3 6
4 6
5 6
6 6
6 7
7 7
7 8

晕了~~~~~~~~~~~~~