最新消息:码丁实验室,一站式儿童编程学习产品,寻地方代理合作共赢,微信联系:leon121393608。

信息学奥赛题库- 积水问题

C++ 少儿编程 1496浏览 0评论

码丁实验室,一站式儿童编程学习产品,寻地方代理合作共赢,微信联系:leon121393608。

【题目描述】

有一块矩形土地被划分成$n×m$个正方形小块。这些小块高低不平,每一小块都有自己的高度。水流可以由任意一块地流向周围四个方向的四块地中,但是不能直接流入对角相连的小块中。

一场大雨后,由于地势高低不同,许多地方都积存了不少降水(这些雨水会不断下,直到积水不再上升)。

给定每个小块的高度,求每个小块的积水高度。

注意:假设矩形地外围无限大且高度为0,即从内部流出来的雨水会在外围消失。

【输入】

第一行包含两个非负整数$n,m$。

接下来$n$行每行$m$个整数表示第$i$行第$j$列的小块的高度。

【输出】

输出$n$行,每行$m$个由空格隔开的非负整数,表示每个小块的积水高度。

【输入样例】

3 3
4 4 0
2 1 3
3 3 -1

【输出样例】

0 0 0
0 1 0
0 0 1

【提示】

【数据规模与约定】

对于20%的数据,$n,m≤4$。

对于40%的数据,$n,m≤15$。

对于60%的数据,$n,m≤50$。

对于100%的数据,$n,m≤300$,|小块高度|$≤10^9$。

在每一部分数据中,均有一半数据保证小块高度非负。

您必须 登录 才能发表评论!