Tweetuzki 爱伊图
题目背景
Tweetuzki 的教练最近常常在群里发有关「伊图科技」的文章。「伊图科技」是一家专注于计算机视觉技术的上海创业公司,其人脸识别技术在世界处于领先地位。2018 年 6 月,在全球工业界黄金标准 FRVT 测试中,依图在千万分之一误报下识别准确率接近 $99\%$,是全球工业界在此项指标下的最好水平,这是依图科技连续第二年摘得此项竞赛的冠军,也是首个夺得此项竞赛冠军的中国团队。2018 年 11 月 16 日,美国国家标准与技术研究院(NIST)公布了全球权威人脸识别比赛(FRVT)最新报告,依图算法继续保持第一,在千万分之一误报下的识别准确率超过 $99\%$,是目前全球人脸识别技术的最好水平。
更重要的是,伊图科技的创始人,是附中的毕业生——Tweetuzki 的学长呢!人脸识别真的好难呢!Tweetuzki 常常幻想,要是自己的程序能有学长们的亿万分之一厉害,那就很好了呢!
题目描述
Tweetuzki 希望设计出一个程序,这个程序应当能识别输入矩阵中隐藏的数字。
输入的是一个 $r \times c$ 的字符矩阵,矩阵中的元素只有 `. `或 `#`。其中 `#` 可以构成一些数字。输入的矩阵将严格遵守以下规则:
- 除 $1$ 占 $5 \times 1$ 的长方形区域外,其余数字均占 $5 \times 3$ 的长方形区域。
- 相邻两个数字间至少有一列 `.`,即**数字不会贴在一块儿**;且数字**只会左右排放**,不会上下排放。这两点综合起来可以表述为:对于两个数字 $A$ 和 $B$($A$ 在 $B$ 的左侧),若它们在横向上延伸的区间分别为 $[l_A, r_A]$ 和 $[l_B, r_B]$,那么一定满足 $l_B \ge r_A + 2$。
- 数字的组成严格按照如下所列:
```plain
数字的组成方式:
# # # # # # # # . # # # # # # # # # # # # # # # # # # #
# . . # . . # # . # # . . # . . . . # # . # # . # # . #
# # # # # # # # # # # # # # # # . . # # # # # # # # . #
# # . . . . # . . # . . # # . # . . # # . # . . # # . #
# # # # # # # . . # # # # # # # . . # # # # # # # # # #
所代表的数字:
1 2 3 4 5 6 7 8 9 0
```
**数字不会倾斜、放大或缩小。**具体可见样例。
- 除构成数字的长方形区域外,其余位置皆由 `.` 填充。保证所有的 `#` 的连通块一定都能够组成数字,且一定满足上述规则。
由于 Tweetuzki 太弱了,于是向你求助,聪明的你,能不能帮助 Tweetuzki 解决这个问题呢?
输入输出格式
输入格式
第一行两个正整数 $r, c$ $(5 \le r \le 10, 3 \le c \le 10^5)$,表示矩阵的行数和列数。
接下来 $r$ 行,每行输入 $c$ 个字符,用空格隔开,保证只含有 `.` 和 `#` 两种字符。输入矩阵保证合法且一定含有隐藏数字。
输出格式
输出仅包含一行一个只含数字的字符串,**按照顺序**输出这个矩阵中隐藏的数字。
输入输出样例
输入样例 #1
6 10
# . . . . . # . . #
# . . . # . # . . #
# . . . # . # . . #
# . . . # . # . . #
# . . . # . # . . #
. . . . # . . . . .
输出样例 #1
1111
输入样例 #2
8 37
. . . # # # . . . . . . . . . . . . . . . . . . # # # . # . . . . . . . .
. # . # . # . . . . . . . . # # # . . . . . . . # . # . # . . . . . . . .
. # . # # # . . . . . . . . # . . . # # # . . . # # # . # . . # # # . . .
. # . . . # . . . # # # . . # # # . # . # . . . # . # . # . . . . # . . .
. # . # # # . . . . . # . . # . # . # . # . . . # # # . # . . . . # . . .
. # . . . . . . . # # # . . # # # . # . # . . . . . . . . . . . . # . . .
. . . . . . . . . # . . . . . . . . # # # . . . . . . . . . . . . # . . .
. . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . .
输出样例 #2
19260817
输入样例 #3
9 94
# # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# . # . . . . . . . . . . . . . . . . . . . . . . . . # . # . . . . . . . . . . # . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# . # . . . # . . . . . . . . . . . . . . . # # # . . # . # . . . . . . . . . . # # # . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# . # . . . # . . # # # . . . . . . . . . . . . # . . # # # . . . . . . . . . . . . # . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# # # . . . # . . . . # . . . . . . . . . . # # # . . . . # . . . . . . . . . . # # # . . . . . . . . . # . # . . . . . . . # # # . . . . . . # # # . . . . . . . . . # # # . . . . . . . .
. . . . . . # . . # # # . . . . . . . . . . . . # . . . . # . . . . . . . . . . . . . . . . . . . . . . # # # . . . . . . . . . # . . . . . . # . # . . . . . . . . . # . # . . . . . . . .
. . . . . . # . . # . . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . # # # . . . . . . . . . # # # . . . . . . . .
. . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . # . # . . . . . . . . . . . # . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . # # # . . . . . . . . . # # # . . . . . . . .
输出样例 #3
0123456789
说明
### 样例解释
建议复制进记事本(或各种 IDE)中用等宽字体查看。
### 子任务
**_Subtask_ #1 _(30 points)_**:矩阵中仅有数字 $1$。
**_Subtask_ #2 _(30 points)_**:矩阵中不含有数字 $1$ 和 $4$。
**_Subtask_ #3 _(40 points)_**:无特殊性质。