解题思路

题意分析

本题的核心是对一个给定的 $N \times N$ 的非负整数矩阵进行处理。在这个矩阵中，存在一些值为 $0$ 的元素，需要将这些 $0$ 元素替换为矩阵中距离它最近的非零元素。这里的距离是通过曼哈顿距离来衡量的，其计算公式为：$\text{distance} = |i - p| + |j - q|$，其中 $(i, j)$ 和 $(p, q)$ 分别是两个元素在矩阵中的坐标。如果存在多个距离相同的非零元素，那么该 $0$ 元素保持不变。输入包括矩阵的大小 $N$ 以及按行优先顺序给出的矩阵元素值；输出则是经过处理后按行优先顺序排列的矩阵。

解题思路

1. 数据结构定义：
   • 定义 DPNode 结构体，用于存储每个矩阵元素的相关信息。其中 count 表示达到当前最短距离的路径数量，dis 表示到最近非零元素的距离，x 和 y 记录最近非零元素的坐标。
   • 定义二维数组 mat[MAXN][MAXN] 用于存储原始矩阵，dp[MAXN][MAXN] 用于存储每个元素的 DPNode 信息。
   • 定义 dir[][2] 数组来表示四个方向的偏移量，方便在矩阵中进行移动。
2. 初始化矩阵信息：
   • 读取矩阵大小 $N$ 和矩阵元素值到 mat 数组中。
   • 将 dp 数组中所有元素的 dis 初始化为一个较大的值 INF，表示还未找到最短距离。
   • 遍历矩阵，对于非零元素，将其对应的 dp 数组元素的 dis 设为 $0$，count 设为 $1$，并记录其坐标。对于零元素，调用 UL 函数进行初步处理。
3. 向上和向左动态规划计算：
   • UL 函数用于处理矩阵中每个元素向上和向左方向的情况。对于当前元素，如果其上方或左方存在元素，且上方或左方元素到最近非零元素的距离加上 $1$ 小于当前元素的距离，那么更新当前元素的距离、路径数量和最近非零元素的坐标；如果距离相等，则根据一定条件（避免重复计数）更新路径数量。
4. 向下和向右动态规划计算：
   • DR 函数用于处理矩阵中每个元素向下和向右方向的情况。原理与 UL 函数类似，对于当前元素，如果其下方或右方存在元素，且下方或右方元素到最近非零元素的距离加上 $1$ 小于当前元素的距离，那么更新当前元素的距离、路径数量和最近非零元素的坐标；如果距离相等，则根据条件更新路径数量。
5. 输出结果：
   • 遍历矩阵，根据 dp 数组中每个元素的 count 值来决定输出值。如果 count 等于 $1$，说明存在唯一的最近非零元素，输出该最近非零元素的值；否则，输出 $0$。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <math.h>

using namespace std;

#define MAXN 203
#define INF 100000000

struct DPNode{
    int count;
    int dis;
    int x;
    int y;
};

int n;
int mat[MAXN][MAXN];
DPNode dp[MAXN][MAXN];
int dir[][2] = { { 0, -1 }, { 1, 0 }, { -1, 0 }, { 0, 1 } };

void UL(int i, int j)
{
    if (i > 0)//L
    {
        if (dp[i][j].dis > dp[i - 1][j].dis + 1)
        {
            dp[i][j].dis = dp[i - 1][j].dis + 1;
            dp[i][j].count = dp[i - 1][j].count;
            dp[i][j].x = dp[i - 1][j].x;
            dp[i][j].y = dp[i - 1][j].y;
        }
        else if (dp[i][j].dis == dp[i - 1][j].dis + 1)
        {
            if (!(dp[i][j].x == dp[i - 1][j].x&&dp[i][j].y == dp[i - 1][j].y
                &&dp[i][j].count == 1 && dp[i - 1][j].count == 1))
                dp[i][j].count += dp[i - 1][j].count;
        }
    }
    if (j > 0)//U
    {
        if (dp[i][j].dis > dp[i][j - 1].dis + 1)
        {
            dp[i][j].dis = dp[i][j - 1].dis + 1;
            dp[i][j].count = dp[i][j - 1].count;
            dp[i][j].x = dp[i][j - 1].x;
            dp[i][j].y = dp[i][j - 1].y;
        }
        else if (dp[i][j].dis == dp[i][j - 1].dis + 1)
        {
            if (!(dp[i][j].x == dp[i][j - 1].x&&dp[i][j].y == dp[i][j - 1].y
                &&dp[i][j].count == 1 && dp[i][j - 1].count == 1))
                dp[i][j].count += dp[i][j - 1].count;
        }
    }
}

void DR(int i, int j)
{
    if (i < n - 1)//R
    {
        if (dp[i][j].dis > dp[i + 1][j].dis + 1)
        {
            dp[i][j].dis = dp[i + 1][j].dis + 1;
            dp[i][j].count = dp[i + 1][j].count;
            dp[i][j].x = dp[i + 1][j].x;
            dp[i][j].y = dp[i + 1][j].y;
        }
        else if (dp[i][j].dis == dp[i + 1][j].dis + 1)
        {
            if (!(dp[i][j].x == dp[i + 1][j].x&&dp[i][j].y == dp[i + 1][j].y
                &&dp[i][j].count == 1 && dp[i + 1][j].count == 1))
                dp[i][j].count += dp[i + 1][j].count;
        }
    }
    if (j < n - 1)//D
    {
        if (dp[i][j].dis > dp[i][j + 1].dis + 1)
        {
            dp[i][j].dis = dp[i][j + 1].dis + 1;
            dp[i][j].count = dp[i][j + 1].count;
            dp[i][j].x = dp[i][j + 1].x;
            dp[i][j].y = dp[i][j + 1].y;
        }
        else if (dp[i][j].dis == dp[i][j + 1].dis + 1)
        {
            if (!(dp[i][j].x == dp[i][j + 1].x&&dp[i][j].y == dp[i][j + 1].y
                &&dp[i][j].count == 1 && dp[i][j + 1].count == 1))
                dp[i][j].count += dp[i][j + 1].count;
        }
    }
}

int main()
{
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &mat[i][j]);
        for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i][j].dis = INF;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mat[i][j]>0)
                {
                    dp[i][j].dis = 0;
                    dp[i][j].count = 1;
                    dp[i][j].x = i;
                    dp[i][j].y = j;
                }
                else
                {
                    UL(i, j);
                }
            }
        }
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                if (mat[i][j] == 0)
                {
                    DR(i, j);
                }
            }
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n-1; j++)
            {
                printf("%d ", dp[i][j].count == 1 ? mat[dp[i][j].x][dp[i][j].y] : 0);
            }
            printf("%d\n", dp[i][n - 1].count == 1 ? mat[dp[i][n - 1].x][dp[i][n - 1].y] : 0);
        }
    }

    return 0;
}