C语言二维数组最短距离算法优化

本文分析并优化了一段C语言代码，该代码用于计算二维数组中每个元素到最近非零元素的最短距离。

**原始代码：**c#include <stdio.h>#include <math.h>int m;int main() { int distance = 0; int arr[99][99]; int ayy[99][99];

int n;    int number;    scanf_s('%d %d', &n, &m);    for (int i = 0; i < n; i++) {        char line[m + 1];        scanf_s('%s', line);  // 以字符串的形式读取整行数字        for (int j = 0; j < m; j++) {            arr[i][j] = line[j] - '0';  // 将字符转换为数字并存储到二维数组中        }    }

for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            if (arr[i][j] == 1 && ayy[i][j] == 1)                printf('0 ');            else if (ayy[i][j] == 0) {                int minDistance = n + m;  // 初始设定一个较大的值作为最短距离                for (int g = 0; g < n; g++) {                    for (int k = 0; k < m; k++) {                        if (arr[g][k] == 1) {                            distance = abs(i - g) + abs(j - k);                            if (distance < minDistance) {                                minDistance = distance;                            }                        }                    }                }                printf('%d ', minDistance);            }        }        printf('

'); }

return 0;}

优化策略：

避免重复计算: 原始代码在计算最短距离时，每次循环都会重新遍历整个二维数组查找非零元素，导致大量重复计算。优化策略是预先找到所有非零元素的坐标并存储，减少重复遍历。
减少不必要判断: 原始代码中 ayy 数组始终为零，因此可以移除对它的判断。

**优化后的代码:**c#include <stdio.h>#include <stdlib.h>#include <math.h>

struct Point { int x; int y;};

int main() { int distance = 0; int arr[99][99]; int n, m; scanf('%d %d', &n, &m); struct Point points[99*99]; int pointCount = 0; for (int i = 0; i < n; i++) { char line[m + 1]; scanf('%s', line); for (int j = 0; j < m; j++) { arr[i][j] = line[j] - '0'; if (arr[i][j] == 1) { points[pointCount].x = i; points[pointCount].y = j; pointCount++; } } }

for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            int minDistance = n + m;            if (arr[i][j] == 0) {                for (int k = 0; k < pointCount; k++) {                    distance = abs(i - points[k].x) + abs(j - points[k].y);                    if (distance < minDistance) {                        minDistance = distance;                    }                }                printf('%d ', minDistance);            } else {                printf('0 ');            }        }        printf('

'); }

return 0;}

优化效果:

优化后的代码通过预处理非零元素坐标，避免了重复遍历数组，显著减少了计算量，提高了代码执行效率，尤其在处理大规模数组时效果更明显。