题目背景

• 1、本题前 $40$ 分可以暴力 bfs 通过
• 2、想通过全部数据，请使用 倒序并查集

题目描述

你有一个初始全是 1 的大小为 $n \times m$ 的迷宫

• 1、其中 1 表示可通行，0 表示无法通行
• 2、在任何一个为 1 的位置，都可以走到上，下，左，右中，也为 1 的位置

再给你一个大小为 $n \times m$ 的二维数组 $a[][]$

• 1、$a[i][j]$：表示在时刻 $a[i][j]$，位置 $(i, j)$ 的 1 会变成 0
• 2、保证 $a[][]$ 中的 $n \times m$ 个数，是 $1 \sim n \times m$ 的 一个排列

请你输出 $n \times m$ 个数，其中第 $i$ 个数表示：$i$ 时刻结束后，迷宫中连通块的个数

输入格式

第一行包含 $2$ 个整数 $n, m$

接下来 $n$ 行，每行包含 $m$ 个正整数，表示数组 $a[][]$

保证：$a[][]$ 中的 $n \times m$ 个数，是 $1 \sim n \times m$ 的 一个排列

输出格式

输出 $n \times m$ 行，每行一个整数

第 $i$ 个整数表示：$i$ 时刻结束后，迷宫中连通块的个数

3 3
7 3 4
9 2 6
1 8 5

1
1
2
2
3
2
2
1
0

提示

【样例 1 解释】

【数据范围】

• 对于 $40\%$ 数据：$1 \le n, m \le 50$
• 对于 $100\%$ 数据：$1 \le n \times m \le 10^5$

来源