迷宫问题
有哪位大虾帮帮,错哪了?程序代码:
#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; }