#P9779. 分封制

    ID: 6410 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>难度分类提高排序与序列处理直方图最大矩形单调栈构造与建模矩阵构造CF2100

分封制

分封制

题目描述

有一块 nn 行、mm 列的土地,每个儿子已占据一个格子。请把所有格子分给这些儿子,要求每人的封地都是一个矩形,包含他原本所在的格子,且不包含其他儿子;每个格子恰好分给一人。

周王最喜欢的儿子用字母 A 表示,要求他的封地面积尽可能大。有多种最优方案时输出任意一种。

输入格式

从标准输入读入。第一行两个整数 n,mn,m;接下来 nn 行,每行 mm 个字符。

每个大写字母表示一名儿子的初始位置,字母互不相同且保证有 A;. 表示空地。

输出格式

输出 n×mn\times m 的矩阵,保留所有原有大写字母,将每个 . 替换为所属儿子对应的小写字母。

样例 输入

6 8
......X.
.F......
...A....
........
.....P..
..L.....

样例 输出

xxxxxxXx
fFaaaaaa
ffaAaaaa
ffaaaaaa
lllllPpp
llLllppp

数据范围

1≤n,m≤10001\le n,m\le1000。30 分数据满足 n≤10n\le10。

时间限制:2 秒。空间限制:512 MB。