本文共 2033 字，大约阅读时间需要 6 分钟。

题目：

 

 

代码：

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

#define MAX_NUM (100 * 100)

#define MAX_ROW 100 #define MAX_COL 100 #define MIN(a,b) ((a) < (b) ? (a) : (b)) typedef struct loc {     int row;     int col; } loc;

int g_len[MAX_ROW][MAX_COL];

loc g_start; int g_mazesize; int **g_maze = NULL; int g_max_col = 0;

loc g_direction[4] = { {-1, 0}, { 1, 0 }, { 0, -1 }, {0, 1 } };

void init_data(void)

{     for (int i = 0; i < MAX_ROW; i++) {         for (int j = 0; j < MAX_COL; j++) {             g_len[i][j] = INT_MAX;         }     }

    g_len[g_start.row][g_start.col] = 0;

}

void dfs(loc start, int len)

{     int tmp_len = 0;     int i;     loc tmp_loc;     int x;     int y;

    // for 4 directions

    for (i = 0; i < 4; i++) {         x = start.row + g_direction[i].row;         y = start.col + g_direction[i].col;         tmp_len = 0;

        while (x >= 0 && x < g_mazesize && y >= 0 & y < g_max_col && g_maze[x][y] == 0) {

            x = x + g_direction[i].row;             y = y + g_direction[i].col;             tmp_len++;         }

        if (g_len[start.row][start.col] + tmp_len < g_len[x - g_direction[i].row][y - g_direction[i].col]) {

            g_len[x - g_direction[i].row][y - g_direction[i].col] = g_len[start.row][start.col] + tmp_len;             tmp_loc.row = x - g_direction[i].row;             tmp_loc.col = y - g_direction[i].col;             dfs(tmp_loc, g_len[start.row][start.col] + tmp_len);         }      }

}

// row = col ?  mazeSize = mazeColSize no 

int shortestDistance(int** maze, int mazeSize, int* mazeColSize, int* start, int startSize, int* destination, int destinationSize){     g_start.row = start[0];     g_start.col = start[1];     g_mazesize = mazeSize; // max row     g_max_col = mazeColSize[0];     g_maze = maze;

    // printf("g_max_col %d\n", g_max_col);

    init_data();

    dfs(g_start,0);

    // solve_data();     // get_result();

    if (g_len[destination[0]][destination[1]] == INT_MAX) {

        return -1;     }     return g_len[destination[0]][destination[1]]; }

总给&注意事项：

1. 建立对应元素的长度数组，并使用长度作为dfs不循环执行的判断条件 2. 数组行数和列数不一定会相等 3. return distance[dest[0]][dest[1]] == Integer.MAX_VALUE ? -1 : distance[dest[0]][dest[1]]; 减少代码行数 4. 使用x  y 表示行列， 不使用结构体，减少代码量 5. direction命名简洁化

6. 可以尝试使用bfs以及ditrista进行求解

转载地址：http://niloi.baihongyu.com/