首先对于这道题，我们的一个大体思路是将表达式还原出来，之后计算的过程就简单了。我会分成几部分来介绍如何实现，顺便介绍一些坑点
降噪
通过观察样例，我们会发现这个图上有很多讨厌的小黑点。为了寻找数字的部分，我们首先应该做的就是降噪。具体如何做呢？
我提供两种方法——洪水填充和众数滤波器。
洪水填充
我们知道，洪水填充可以用来寻找联通块（不会的去P1596）。那么，根据题目给出的 （颜色反转概率）并不大来看，可以预想到的是不会出现面积超过 的联通快，那么洪水填充并将联通块面积小于 的变成白色即可。
但是，如果你采用这种方法可能会在第 号点 WA 掉。这是因为虽然噪点不会超过 ，但是原本要被识别的运算符或数字可能被割开。我提供一组 hack(感谢 reveal 大佬指出)：
......#..............#.#.................
.......#..........####................#..
..........######.#....##..........#......
....#.##..........####...................
.....#..#...#..###..#####................
...........#.####.#######.............#..
.....#.#####.####.##.###......#......#...
....#####.#######..###.....#.............
.....####.#######...........##...........
.....##.#####.#...#.....#..............#.
.....#####.................#...#.........
.....#####....#..........................
.....#####...........#............#......
........###......#...............#.......
....#.#####.........#.....#..............
...#..#####.....###.###.###..............
......##......######.##.###..............
.........###########.####.##..........#..
.....#####..#####.#.#######........#.....
.....######.#######.###.##.#.........#.#.
.....######.###.####.#######..........#..
.....##.#######....#.#######.............
......######....#..#.######.##...........
......######............####.............
...#..##.##............#....#........#...
........................##.##............
..#....................#####.#...........
.......................#.#####...........
.........#...#..........######.........#.
...................#...#######...........
.....................#.##.##.##..........
......................##..####......#....
.........#...........##.######......#....
..........#####.#.#####.#####............
.........######.#######.#####..#........#
......#.######...####.#..####.#..........
.......#####.###.######.#................
#......#.######.#####....................
......#.#######.#.#..#.#...........#.....
........#####...........#..............#.
..#......................................
..................................#......
可以发现 在中间被分割成了两部分，这导致会识别错误。
但洪水填充是有用的，会在接下来说明用途。
众数滤波器
这个东西听着高级，实际上就是比较。
对于坐标 ，我们比较 周围 个方向还有自己的黑色点数量与白色点数量。之后黑色点数目多就将新图片的 设为黑色，否则为白色。
这样最多一个数字或运算符的边缘会被削掉，但是整体图片的形状不会受影响。
分离
经过降噪之后，我们就要去分离了。
这时候洪水填充就派上用场了。我们用洪水填充去确定每一个数字或运算符的范围，并将其分离成多份去分别操作，这样可以使我们将每一个数字或运算符逐一击破。
变换
最难的部分要来了。对于本题的匹配，可以发现从原图尝试复原到标准字体不太现实，因为会丢失很多信息也不太好写。我们不如反过来。因为题目给出了变换规则，所以我们不妨随机一些参数来尝试从标准字体来还原。
所以我们根据题目模拟即可。
匹配率
现在我们有了两个图像，一个是由标准变来的，一个是待匹配的。我们现在需要比对了。
在比对之前，我们要先将两个图像居中，这样才不会出现一个3经过旋转到了左上角但分离出来的居中的情况。
之后就比对即可。匹配率用 即可。为了统一都将图片变成 的格式。
训练+查找
之后我们设定一个 train_time 来表示随机的次数，次数越高准确率越高。但是 TLE 的可能也就越大。我这里默认的是 次，但是测试点编号大于 的我改成了 ，保证准确率。具体的可以根据你程序的常数来决定。
之后对于每一次随机，做 次随机变换。从范围生成参数然后变换出图片。之后将每一次变换的图片都存下来。这也是一个优化的技巧。因为变换是有一个复杂度的，提前收集下来可以为了之后查找的效率快一点。不需要每一次都重新生成。
之后匹配就把每一张图片跟现在的待查找图片去求匹配率，然后将匹配率最高的字符设定为当前的字符。
总代码
#include <bits/stdc++.h>
#include <random>
#define Operator O
using namespace std;
typedef long long ll;
const ll MAXH = 65 + 5;
const ll MAXW = 9000 + 5;
const double pi = 3.1415926535;
ll train_time = 270;
double radian(double d) {
return d / 180.0 * pi;
}
struct image {
ll x, y;
string s[MAXH];
image() {
x = 0, y = 0;
}
image(ll _x, ll _y) :
x(_x),
y(_y) {
for (int i = 1; i <= x; ++i) {
s[i] = " ";
for (int j = 1; j <= y; ++j) {
s[i] += '.';
}
}
}
};
vector<image> ex;
image Operator[20];
image change_middle(image im) {
image New(65, 38);
ll mx = im.x, my = im.y;
ll px = (65 - mx) / 2, py = (38 - my) / 2;
for (int i = 1; i <= im.x; ++i) {
for (int j = 1; j <= im.y; ++j) {
if (i + px <= 65 && i + px >= 1 && j + py <= 38 && j + py >= 1) {
New.s[i + px][j + py] = im.s[i][j];
}
}
}
return New;
}
namespace Init {
image input;
bool vis[MAXH][MAXW];
struct separate_information {
ll min_x = 1e18, max_x = -1e18, min_y = 1e18, max_y = -1e18;
void Return() {
min_x = 1e18, max_x = -1e18, min_y = 1e18, max_y = -1e18;
}
void turn(ll x, ll y) {
min_x = min(min_x, x);
max_x = max(max_x, x);
min_y = min(min_y, y);
max_y = max(max_y, y);
}
bool operator<(const separate_information &K) const {
return min_y < K.min_y;
}
} Si[1000];
ll cc = 1;
ll val;
ll dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
ll dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
void flood_fill(ll x, ll y, bool del) {
if (del) {
input.s[x][y] = '.';
} else {
Si[cc].turn(x, y);
vis[x][y] = true;
val++;
}
for (int i = 0; i < 8; ++i) {
ll X = x + dx[i], Y = y + dy[i];
if (X < 1 || X > input.x || Y < 1 || Y > input.y || (vis[X][Y] && !del) || input.s[X][Y] == '.') {
continue;
}
flood_fill(X, Y, del);
}
}
vector<image> clean() {
cc = 1;
memset(vis, false, sizeof(vis));
image New(input.x, input.y);
for (int i = 1; i <= input.x; ++i) {
for (int j = 1; j <= input.y; ++j) {
ll bn = 0, wn = 0;
if (input.s[i][j] == '#') {
bn = 1;
} else {
wn = 1;
}
for (int k = 0; k < 8; ++k) {
ll X = i + dx[k], Y = j + dy[k];
if (X < 1 || X > input.x || Y < 1 || Y > input.y) {
continue;
}
if (input.s[X][Y] == '#') {
bn++;
} else {
wn++;
}
}
if (bn > wn) {
New.s[i][j] = '#';
} else {
New.s[i][j] = '.';
}
}
}
input = New;
for (int i = 1; i <= input.x; ++i) {
for (int j = 1; j <= input.y; ++j) {
if (input.s[i][j] == '#' && !vis[i][j]) {
val = 0;
Si[cc].Return();
flood_fill(i, j, false);
if (val < 50) {
flood_fill(i, j, true);
continue;
}
cc++;
}
}
}
vector<image> SI;
sort(Si + 1, Si + cc);
for (int i = 1; i < cc; ++i) {
separate_information si = Si[i];
image each(si.max_x - si.min_x + 1, si.max_y - si.min_y + 1);
ll sz = 1;
for (int k = si.min_x; k <= si.max_x; ++k) {
each.s[sz] = " ";
for (int l = si.min_y; l <= si.max_y; ++l) {
each.s[sz] += input.s[k][l];
}
++sz;
}
SI.push_back(each);
}
return SI;
}
void init() {
O[0].x = 39, O[0].y = 30, O[0].s[1] = " ...........########...........", O[0].s[2] = " .........############.........", O[0].s[3] = " .......################.......", O[0].s[4] = " ......##################......", O[0].s[5] = " .....####################.....", O[0].s[6] = " ....######################....", O[0].s[7] = " ...########################...", O[0].s[8] = " ...##########....##########...", O[0].s[9] = " ..#########........#########..", O[0].s[10] = " ..########..........########..", O[0].s[11] = " .#########..........#########.", O[0].s[12] = " .########............########.", O[0].s[13] = " .########............########.", O[0].s[14] = " .########............########.", O[0].s[15] = " ########..............########", O[0].s[16] = " ########..............########", O[0].s[17] = " ########..............########", O[0].s[18] = " ########..............########", O[0].s[19] = " ########..............########", O[0].s[20] = " ########..............########", O[0].s[21] = " ########..............########", O[0].s[22] = " ########..............########", O[0].s[23] = " ########..............########", O[0].s[24] = " ########..............########", O[0].s[25] = " ########..............########", O[0].s[26] = " .########............########.", O[0].s[27] = " .########............########.", O[0].s[28] = " .########............########.", O[0].s[29] = " .#########..........#########.", O[0].s[30] = " ..########..........########..", O[0].s[31] = " ..#########........#########..", O[0].s[32] = " ...##########....##########...", O[0].s[33] = " ...########################...", O[0].s[34] = " ....######################....", O[0].s[35] = " .....####################.....", O[0].s[36] = " ......##################......", O[0].s[37] = " .......################.......", O[0].s[38] = " .........############.........", O[0].s[39] = " ...........########...........";
O[1].x = 38, O[1].y = 27, O[1].s[1] = " .............####..........", O[1].s[2] = " ...........#######.........", O[1].s[3] = " ........##########.........", O[1].s[4] = " .....#############.........", O[1].s[5] = " ..################.........", O[1].s[6] = " .#################.........", O[1].s[7] = " .#################.........", O[1].s[8] = " .#################.........", O[1].s[9] = " .#################.........", O[1].s[10] = " ..######..########.........", O[1].s[11] = " ..###.....########.........", O[1].s[12] = " ..........########.........", O[1].s[13] = " ..........########.........", O[1].s[14] = " ..........########.........", O[1].s[15] = " ..........########.........", O[1].s[16] = " ..........########.........", O[1].s[17] = " ..........########.........", O[1].s[18] = " ..........########.........", O[1].s[19] = " ..........########.........", O[1].s[20] = " ..........########.........", O[1].s[21] = " ..........########.........", O[1].s[22] = " ..........########.........", O[1].s[23] = " ..........########.........", O[1].s[24] = " ..........########.........", O[1].s[25] = " ..........########.........", O[1].s[26] = " ..........########.........", O[1].s[27] = " ..........########.........", O[1].s[28] = " ..........########.........", O[1].s[29] = " ..........########.........", O[1].s[30] = " ..........########.........", O[1].s[31] = " ..........########.........", O[1].s[32] = " ..........########.........", O[1].s[33] = " .##########################", O[1].s[34] = " ###########################", O[1].s[35] = " ###########################", O[1].s[36] = " ###########################", O[1].s[37] = " ###########################", O[1].s[38] = " .##########################";
O[2].x = 38, O[2].y = 28, O[2].s[1] = " .........#########..........", O[2].s[2] = " ......##############........", O[2].s[3] = " ...###################......", O[2].s[4] = " ..#####################.....", O[2].s[5] = " .#######################....", O[2].s[6] = " .#######################....", O[2].s[7] = " .########################...", O[2].s[8] = " .#########......#########...", O[2].s[9] = " .#######.........#########..", O[2].s[10] = " .#######..........########..", O[2].s[11] = " .#######..........########..", O[2].s[12] = " .#######..........########..", O[2].s[13] = " .#######..........########..", O[2].s[14] = " ..######..........########..", O[2].s[15] = " .................#########..", O[2].s[16] = " .................########...", O[2].s[17] = " ................#########...", O[2].s[18] = " ...............##########...", O[2].s[19] = " ..............##########....", O[2].s[20] = " .............###########....", O[2].s[21] = " ............###########.....", O[2].s[22] = " ...........###########......", O[2].s[23] = " ..........###########.......", O[2].s[24] = " .........###########........", O[2].s[25] = " ........###########.........", O[2].s[26] = " .......###########..........", O[2].s[27] = " ......###########.....#####.", O[2].s[28] = " .....###########.....#######", O[2].s[29] = " ....###########......#######", O[2].s[30] = " ...###########.......#######", O[2].s[31] = " ..###########........#######", O[2].s[32] = " .###########.........#######", O[2].s[33] = " ############################", O[2].s[34] = " ############################", O[2].s[35] = " ############################", O[2].s[36] = " ############################", O[2].s[37] = " ############################", O[2].s[38] = " .###########################";
O[3].x = 39, O[3].y = 28, O[3].s[1] = " .........##########.........", O[3].s[2] = " .....################.......", O[3].s[3] = " ...####################.....", O[3].s[4] = " ..######################....", O[3].s[5] = " ..#######################...", O[3].s[6] = " ..########################..", O[3].s[7] = " ..########################..", O[3].s[8] = " ..########.......##########.", O[3].s[9] = " ..#######.........#########.", O[3].s[10] = " ..#######..........########.", O[3].s[11] = " ..#######..........########.", O[3].s[12] = " ...######..........########.", O[3].s[13] = " ...................########.", O[3].s[14] = " ...................########.", O[3].s[15] = " ..................########..", O[3].s[16] = " .................#########..", O[3].s[17] = " ..........###############...", O[3].s[18] = " .........###############....", O[3].s[19] = " .........##############.....", O[3].s[20] = " .........###############....", O[3].s[21] = " .........################...", O[3].s[22] = " ..........################..", O[3].s[23] = " .................##########.", O[3].s[24] = " ...................########.", O[3].s[25] = " ...................#########", O[3].s[26] = " ....................########", O[3].s[27] = " ....................########", O[3].s[28] = " ....................########", O[3].s[29] = " ....................########", O[3].s[30] = " ...................#########", O[3].s[31] = " ..###.............##########", O[3].s[32] = " .########........##########.", O[3].s[33] = " .##########################.", O[3].s[34] = " .#########################..", O[3].s[35] = " ##########################..", O[3].s[36] = " .########################...", O[3].s[37] = " .######################.....", O[3].s[38] = " ....#################.......", O[3].s[39] = " .......###########..........";
O[4].x = 38, O[4].y = 30, O[4].s[1] = " .................#####........", O[4].s[2] = " ................#######.......", O[4].s[3] = " ...............########.......", O[4].s[4] = " ..............#########.......", O[4].s[5] = " .............##########.......", O[4].s[6] = " ............###########.......", O[4].s[7] = " ............###########.......", O[4].s[8] = " ...........############.......", O[4].s[9] = " ..........#############.......", O[4].s[10] = " .........##############.......", O[4].s[11] = " ........###############.......", O[4].s[12] = " .......################.......", O[4].s[13] = " .......########.#######.......", O[4].s[14] = " ......########..#######.......", O[4].s[15] = " .....########...#######.......", O[4].s[16] = " ....########....#######.......", O[4].s[17] = " ...#########....#######.......", O[4].s[18] = " ...########.....#######.......", O[4].s[19] = " ..########......#######.......", O[4].s[20] = " .########.......#######.......", O[4].s[21] = " ##############################", O[4].s[22] = " ##############################", O[4].s[23] = " ##############################", O[4].s[24] = " ##############################", O[4].s[25] = " ##############################", O[4].s[26] = " ##############################", O[4].s[27] = " ...............########.......", O[4].s[28] = " ...............########.......", O[4].s[29] = " ...............########.......", O[4].s[30] = " ...............########.......", O[4].s[31] = " ...............########.......", O[4].s[32] = " ...............########.......", O[4].s[33] = " .........####################.", O[4].s[34] = " ........#####################.", O[4].s[35] = " ........#####################.", O[4].s[36] = " ........#####################.", O[4].s[37] = " ........#####################.", O[4].s[38] = " .........####################.";
O[5].x = 38, O[5].y = 28, O[5].s[1] = " ...######################...", O[5].s[2] = " ...#######################..", O[5].s[3] = " ...#######################..", O[5].s[4] = " ...#######################..", O[5].s[5] = " ...#######################..", O[5].s[6] = " ...######################...", O[5].s[7] = " ...#######..................", O[5].s[8] = " ...#######..................", O[5].s[9] = " ...#######..................", O[5].s[10] = " ...#######..................", O[5].s[11] = " ...#######..................", O[5].s[12] = " ...#######..................", O[5].s[13] = " ..########..########........", O[5].s[14] = " ..####################......", O[5].s[15] = " ..######################....", O[5].s[16] = " ..#######################...", O[5].s[17] = " ..########################..", O[5].s[18] = " ..########################..", O[5].s[19] = " ..#########################.", O[5].s[20] = " ..########.......##########.", O[5].s[21] = " .....##...........#########.", O[5].s[22] = " ...................#########", O[5].s[23] = " ....................########", O[5].s[24] = " ....................########", O[5].s[25] = " ....................########", O[5].s[26] = " ....................########", O[5].s[27] = " ....................########", O[5].s[28] = " ....................########", O[5].s[29] = " ...#...............#########", O[5].s[30] = " ..####............#########.", O[5].s[31] = " .########.......###########.", O[5].s[32] = " .##########################.", O[5].s[33] = " .#########################..", O[5].s[34] = " #########################...", O[5].s[35] = " .#######################....", O[5].s[36] = " ..#####################.....", O[5].s[37] = " ....#################.......", O[5].s[38] = " ........##########..........";
O[6].x = 39, O[6].y = 29, O[6].s[1] = " ....................######...", O[6].s[2] = " ...............###########...", O[6].s[3] = " ............###############..", O[6].s[4] = " ..........#################..", O[6].s[5] = " ........###################..", O[6].s[6] = " .......####################..", O[6].s[7] = " ......####################...", O[6].s[8] = " .....################........", O[6].s[9] = " ....############.............", O[6].s[10] = " ...###########...............", O[6].s[11] = " ...#########.................", O[6].s[12] = " ..#########..................", O[6].s[13] = " ..########...................", O[6].s[14] = " .########....................", O[6].s[15] = " .########....................", O[6].s[16] = " .#######....########.........", O[6].s[17] = " .#######..#############......", O[6].s[18] = " #########################....", O[6].s[19] = " ##########################...", O[6].s[20] = " ###########################..", O[6].s[21] = " ###########################..", O[6].s[22] = " ############......##########.", O[6].s[23] = " ##########.........#########.", O[6].s[24] = " #########...........#########", O[6].s[25] = " ########.............########", O[6].s[26] = " ########.............########", O[6].s[27] = " ########.............########", O[6].s[28] = " .#######.............########", O[6].s[29] = " .#######.............########", O[6].s[30] = " .########...........#########", O[6].s[31] = " .#########.........#########.", O[6].s[32] = " ..##########.....###########.", O[6].s[33] = " ...#########################.", O[6].s[34] = " ...########################..", O[6].s[35] = " ....######################...", O[6].s[36] = " .....####################....", O[6].s[37] = " ......##################.....", O[6].s[38] = " ........##############.......", O[6].s[39] = " ...........########..........";
O[7].x = 38, O[7].y = 28, O[7].s[1] = " ###########################.", O[7].s[2] = " ############################", O[7].s[3] = " ############################", O[7].s[4] = " ############################", O[7].s[5] = " ############################", O[7].s[6] = " ###########################.", O[7].s[7] = " #######...........#########.", O[7].s[8] = " #######...........#########.", O[7].s[9] = " #######..........#########..", O[7].s[10] = " #######..........#########..", O[7].s[11] = " #######..........########...", O[7].s[12] = " #######.........#########...", O[7].s[13] = " #######.........########....", O[7].s[14] = " #######........#########....", O[7].s[15] = " .#####.........#########....", O[7].s[16] = " ...............########.....", O[7].s[17] = " ..............#########.....", O[7].s[18] = " ..............########......", O[7].s[19] = " .............#########......", O[7].s[20] = " .............########.......", O[7].s[21] = " ............#########.......", O[7].s[22] = " ............#########.......", O[7].s[23] = " ............########........", O[7].s[24] = " ...........#########........", O[7].s[25] = " ...........########.........", O[7].s[26] = " ..........#########.........", O[7].s[27] = " ..........########..........", O[7].s[28] = " ..........########..........", O[7].s[29] = " .........########...........", O[7].s[30] = " .........########...........", O[7].s[31] = " ........#########...........", O[7].s[32] = " ........########............", O[7].s[33] = " ........########............", O[7].s[34] = " .......########.............", O[7].s[35] = " .......########.............", O[7].s[36] = " .......#######..............", O[7].s[37] = " .......#######..............", O[7].s[38] = " .........#####..............";
O[8].x = 39, O[8].y = 28, O[8].s[1] = " ..........#########.........", O[8].s[2] = " ........#############.......", O[8].s[3] = " ......#################.....", O[8].s[4] = " .....###################....", O[8].s[5] = " ....#####################...", O[8].s[6] = " ...#######################..", O[8].s[7] = " ...#######################..", O[8].s[8] = " ...#########.....#########..", O[8].s[9] = " ..#########.......#########.", O[8].s[10] = " ..########.........########.", O[8].s[11] = " ..########.........########.", O[8].s[12] = " ..########.........########.", O[8].s[13] = " ..########.........########.", O[8].s[14] = " ..########.........########.", O[8].s[15] = " ...########.......########..", O[8].s[16] = " ...#########.....#########..", O[8].s[17] = " ....#####################...", O[8].s[18] = " .....###################....", O[8].s[19] = " ......#################.....", O[8].s[20] = " ......#################.....", O[8].s[21] = " ....#####################...", O[8].s[22] = " ...#######################..", O[8].s[23] = " ..#########......##########.", O[8].s[24] = " .########..........########.", O[8].s[25] = " .########..........#########", O[8].s[26] = " ########............########", O[8].s[27] = " ########............########", O[8].s[28] = " ########............########", O[8].s[29] = " ########............########", O[8].s[30] = " #########..........#########", O[8].s[31] = " #########..........#########", O[8].s[32] = " .##########......##########.", O[8].s[33] = " .##########################.", O[8].s[34] = " ..########################..", O[8].s[35] = " ..########################..", O[8].s[36] = " ...######################...", O[8].s[37] = " ....####################....", O[8].s[38] = " ......################......", O[8].s[39] = " .........##########.........";
O[9].x = 39, O[9].y = 28, O[9].s[1] = " .........#########..........", O[9].s[2] = " .......#############........", O[9].s[3] = " .....#################......", O[9].s[4] = " ....###################.....", O[9].s[5] = " ...#####################....", O[9].s[6] = " ..#######################...", O[9].s[7] = " .########################...", O[9].s[8] = " .##########......#########..", O[9].s[9] = " .#########........#########.", O[9].s[10] = " #########..........########.", O[9].s[11] = " ########............#######.", O[9].s[12] = " ########............#######.", O[9].s[13] = " ########............########", O[9].s[14] = " ########............########", O[9].s[15] = " ########............########", O[9].s[16] = " #########..........#########", O[9].s[17] = " .########.........##########", O[9].s[18] = " .##########......###########", O[9].s[19] = " ..##########################", O[9].s[20] = " ..##########################", O[9].s[21] = " ...#########################", O[9].s[22] = " ....########################", O[9].s[23] = " ......############..########", O[9].s[24] = " ........########....#######.", O[9].s[25] = " ....................#######.", O[9].s[26] = " ...................########.", O[9].s[27] = " ...................########.", O[9].s[28] = " ..................########..", O[9].s[29] = " .................#########..", O[9].s[30] = " ...............##########...", O[9].s[31] = " .............############...", O[9].s[32] = " .........###############....", O[9].s[33] = " ....###################.....", O[9].s[34] = " ...###################......", O[9].s[35] = " ...##################.......", O[9].s[36] = " ...################.........", O[9].s[37] = " ...##############...........", O[9].s[38] = " ...############.............", O[9].s[39] = " ....######..................";
O[10].x = 54, O[10].y = 21, O[10].s[1] = " ..####...............", O[10].s[2] = " .######..............", O[10].s[3] = " #########............", O[10].s[4] = " ##########...........", O[10].s[5] = " ###########..........", O[10].s[6] = " ############.........", O[10].s[7] = " .############........", O[10].s[8] = " ...###########.......", O[10].s[9] = " ....###########......", O[10].s[10] = " .....##########......", O[10].s[11] = " ......##########.....", O[10].s[12] = " .......##########....", O[10].s[13] = " ........#########....", O[10].s[14] = " .........#########...", O[10].s[15] = " ..........########...", O[10].s[16] = " ..........#########..", O[10].s[17] = " ...........########..", O[10].s[18] = " ...........#########.", O[10].s[19] = " ............########.", O[10].s[20] = " ............########.", O[10].s[21] = " ............########.", O[10].s[22] = " ............#########", O[10].s[23] = " .............########", O[10].s[24] = " .............########", O[10].s[25] = " .............########", O[10].s[26] = " .............########", O[10].s[27] = " .............########", O[10].s[28] = " .............########", O[10].s[29] = " .............########", O[10].s[30] = " .............########", O[10].s[31] = " .............########", O[10].s[32] = " .............########", O[10].s[33] = " ............########.", O[10].s[34] = " ............########.", O[10].s[35] = " ............########.", O[10].s[36] = " ...........#########.", O[10].s[37] = " ...........########..", O[10].s[38] = " ..........#########..", O[10].s[39] = " ..........#########..", O[10].s[40] = " .........#########...", O[10].s[41] = " ........##########...", O[10].s[42] = " .......##########....", O[10].s[43] = " .......#########.....", O[10].s[44] = " .....###########.....", O[10].s[45] = " ....###########......", O[10].s[46] = " ...###########.......", O[10].s[47] = " ..###########........", O[10].s[48] = " ############.........", O[10].s[49] = " ###########..........", O[10].s[50] = " ##########...........", O[10].s[51] = " #########............", O[10].s[52] = " .#######.............", O[10].s[53] = " ..####...............", O[10].s[54] = " ...#.................";
O[11].x = 51, O[11].y = 28, O[11].s[1] = " ......................####..", O[11].s[2] = " ......................######", O[11].s[3] = " .....................#######", O[11].s[4] = " .....................#######", O[11].s[5] = " ....................########", O[11].s[6] = " ....................#######.", O[11].s[7] = " ...................########.", O[11].s[8] = " ...................#######..", O[11].s[9] = " ..................########..", O[11].s[10] = " ..................#######...", O[11].s[11] = " .................########...", O[11].s[12] = " .................#######....", O[11].s[13] = " ................########....", O[11].s[14] = " ................########....", O[11].s[15] = " ................#######.....", O[11].s[16] = " ...............########.....", O[11].s[17] = " ...............#######......", O[11].s[18] = " ..............########......", O[11].s[19] = " ..............#######.......", O[11].s[20] = " .............########.......", O[11].s[21] = " .............#######........", O[11].s[22] = " ............########........", O[11].s[23] = " ............#######.........", O[11].s[24] = " ...........########.........", O[11].s[25] = " ...........#######..........", O[11].s[26] = " ..........########..........", O[11].s[27] = " ..........#######...........", O[11].s[28] = " ..........#######...........", O[11].s[29] = " .........########...........", O[11].s[30] = " .........#######............", O[11].s[31] = " ........########............", O[11].s[32] = " ........#######.............", O[11].s[33] = " .......########.............", O[11].s[34] = " .......#######..............", O[11].s[35] = " ......########..............", O[11].s[36] = " ......#######...............", O[11].s[37] = " .....########...............", O[11].s[38] = " .....#######................", O[11].s[39] = " ....########................", O[11].s[40] = " ....#######.................", O[11].s[41] = " ...########.................", O[11].s[42] = " ...########.................", O[11].s[43] = " ...#######..................", O[11].s[44] = " ..########..................", O[11].s[45] = " ..#######...................", O[11].s[46] = " .########...................", O[11].s[47] = " .#######....................", O[11].s[48] = " ########....................", O[11].s[49] = " #######.....................", O[11].s[50] = " .######.....................", O[11].s[51] = " ..#####.....................";
O[12].x = 7, O[12].y = 28, O[12].s[1] = " .##########################.", O[12].s[2] = " ############################", O[12].s[3] = " ############################", O[12].s[4] = " ############################", O[12].s[5] = " ############################", O[12].s[6] = " ############################", O[12].s[7] = " .###########################";
O[13].x = 54, O[13].y = 21, O[13].s[1] = " ...............####..", O[13].s[2] = " ..............######.", O[13].s[3] = " ............########.", O[13].s[4] = " ...........##########", O[13].s[5] = " ..........###########", O[13].s[6] = " .........############", O[13].s[7] = " ........############.", O[13].s[8] = " .......###########...", O[13].s[9] = " ......###########....", O[13].s[10] = " .....###########.....", O[13].s[11] = " .....##########......", O[13].s[12] = " ....##########.......", O[13].s[13] = " ....#########........", O[13].s[14] = " ...#########.........", O[13].s[15] = " ...########..........", O[13].s[16] = " ..#########..........", O[13].s[17] = " ..########...........", O[13].s[18] = " .#########...........", O[13].s[19] = " .########............", O[13].s[20] = " .########............", O[13].s[21] = " .########............", O[13].s[22] = " #########............", O[13].s[23] = " ########.............", O[13].s[24] = " ########.............", O[13].s[25] = " ########.............", O[13].s[26] = " ########.............", O[13].s[27] = " ########.............", O[13].s[28] = " ########.............", O[13].s[29] = " ########.............", O[13].s[30] = " ########.............", O[13].s[31] = " ########.............", O[13].s[32] = " ########.............", O[13].s[33] = " .########............", O[13].s[34] = " .########............", O[13].s[35] = " .########............", O[13].s[36] = " .#########...........", O[13].s[37] = " ..########...........", O[13].s[38] = " ..#########..........", O[13].s[39] = " ..#########..........", O[13].s[40] = " ...#########.........", O[13].s[41] = " ...##########........", O[13].s[42] = " ....#########........", O[13].s[43] = " .....#########.......", O[13].s[44] = " .....##########......", O[13].s[45] = " ......###########....", O[13].s[46] = " .......###########...", O[13].s[47] = " ........###########..", O[13].s[48] = " .........############", O[13].s[49] = " ..........###########", O[13].s[50] = " ...........##########", O[13].s[51] = " ............#########", O[13].s[52] = " .............#######.", O[13].s[53] = " ...............####..", O[13].s[54] = " .................#...";
O[14].x = 28, O[14].y = 27, O[14].s[1] = " ...........#####...........", O[14].s[2] = " ..........#######..........", O[14].s[3] = " ..........#######..........", O[14].s[4] = " ..........#######..........", O[14].s[5] = " ..........#######..........", O[14].s[6] = " ..........#######..........", O[14].s[7] = " ..........#######..........", O[14].s[8] = " ..........#######..........", O[14].s[9] = " ..........#######..........", O[14].s[10] = " ..........#######..........", O[14].s[11] = " ###########################", O[14].s[12] = " ###########################", O[14].s[13] = " ###########################", O[14].s[14] = " ###########################", O[14].s[15] = " ###########################", O[14].s[16] = " ###########################", O[14].s[17] = " ###########################", O[14].s[18] = " ..........#######..........", O[14].s[19] = " ..........#######..........", O[14].s[20] = " ..........#######..........", O[14].s[21] = " ..........#######..........", O[14].s[22] = " ..........#######..........", O[14].s[23] = " ..........#######..........", O[14].s[24] = " ..........#######..........", O[14].s[25] = " ..........#######..........", O[14].s[26] = " ..........#######..........", O[14].s[27] = " ..........#######..........", O[14].s[28] = " ...........#####...........";
O[15].x = 26, O[15].y = 26, O[15].s[1] = " ...........####...........", O[15].s[2] = " ..........######..........", O[15].s[3] = " ..........#######.........", O[15].s[4] = " .........########.........", O[15].s[5] = " .........########.........", O[15].s[6] = " ..........#######.........", O[15].s[7] = " ..........######..........", O[15].s[8] = " .#####....######.....####.", O[15].s[9] = " .######...######...#######", O[15].s[10] = " #########..#####.#########", O[15].s[11] = " ###############.##########", O[15].s[12] = " ##########################", O[15].s[13] = " ##########################", O[15].s[14] = " .########################.", O[15].s[15] = " ......##############......", O[15].s[16] = " .........########.........", O[15].s[17] = " ........###########.......", O[15].s[18] = " .......#############......", O[15].s[19] = " .....########.#######.....", O[15].s[20] = " ....########..########....", O[15].s[21] = " ....########..#########...", O[15].s[22] = " ...########....########...", O[15].s[23] = " ...########....########...", O[15].s[24] = " ....#######.....#######...", O[15].s[25] = " .....#####......######....", O[15].s[26] = " ......###.........##......";
for (int i = 0; i < 16; ++i) {
Operator[i] = change_middle(Operator[i]);
}
ll t;
scanf("%lld", &t);
if (t >= 90) {
train_time = 143;
}
scanf("%lld%lld", &input.y, &input.x);
for (int i = 1; i <= 65; ++i) {
cin >> input.s[i];
input.s[i] = " " + input.s[i];
}
}
}
using Init::clean;
image change(image query, double M, double M_h, double M_w, double R, double S_x, double S_y) {
image New(65, 38);
double Cos = cos(radian(R)), Sin = sin(radian(R));
for (int i = 1; i <= query.x; ++i) {
for (int j = 1; j <= query.y; ++j) {
if (query.s[i][j] == '#') {
double x = i + 0.5 - 32.5, y = j + 0.5 - 19;
x *= M * M_w;
y *= M * M_h;
double spin_x = x * Cos - y * Sin;
double spin_y = x * Sin + y * Cos;
x = spin_x + S_y * spin_y;
y = spin_y + S_x * spin_x;
x = floor(x + 32);
y = floor(y + 18.5);
ll X = x, Y = y;
if (X >= 1 && X <= 65 && Y >= 1 && Y <= 38) {
New.s[X][Y] = '#';
}
}
}
}
Init::input = change_middle(New);
vector<image> EX = clean();
return change_middle(EX[0]);
}
double same(image query, image simple) {
ll val = 0;
for (int i = 1; i <= 65; ++i) {
for (int j = 1; j <= 38; ++j) {
val += (query.s[i][j] == simple.s[i][j]);
}
}
return val * 1.0 / 2470;
}
image random_image[5000 + 5][20];
void Train() {
random_device rd;
mt19937 random_seed(rd());
uniform_real_distribution<> rm(0.9, 1), rr(-15, 15), rs(-0.1, 0.1);
for (int i = 0; i < train_time; ++i) {
for (int j = 0; j < 16; ++j) {
double M = rm(random_seed);
double M_h = rm(random_seed), M_w = rm(random_seed);
double R = rr(random_seed);
double S_x = rs(random_seed), S_y = rs(random_seed);
random_image[i][j] = change(Operator[j], M, M_h, M_w, R, S_x, S_y);
}
}
}
char to(image im, char c) {
char ac[] = "0123456789)/-(+*";
im = change_middle(im);
double fit_rate = 0;
ll id;
for (int i = 0; i < train_time; ++i) {
for (int j = 0; j < 16; ++j) {
if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(') {
if (ac[j] == '+' || ac[j] == '-' || ac[j] == '*' || ac[j] == '/' || ac[j] == ')') {
continue;
}
}
if (isdigit(c)) {
if (isdigit(ac[j]) || ac[j] == '(') {
continue;
}
}
if (c == ')') {
if (ac[j] == '(' || isdigit(ac[j])) {
continue;
}
}
if (c == '(' && ac[j] == ')') {
continue;
}
double new_fit_rate = same(random_image[i][j], im);
if (new_fit_rate > fit_rate) {
fit_rate = new_fit_rate;
id = j;
}
}
}
return ac[id];
}
namespace Calc {
stack <ll> num;
stack<char> op;
ll g(char a) {
if (a == '+' || a == '-') {
return 1;
} else if (a == '*' || a == '/') {
return 2;
}
return 0;
}
void Do() {
ll a, b, c;
char o = op.top();
op.pop();
a = num.top();
num.pop();
b = num.top();
num.pop();
if (o == '+') {
c = a + b;
} else if (o == '-') {
c = b - a;
} else if (o == '*') {
c = a * b;
} else {
c = b / a;
}
num.push(c);
}
ll Ans(string expression) {
for (int i = 0; i < expression.size(); ++i) {
char c = expression[i];
if (isdigit(c)) {
num.push(c - '0');
} else if (c == '(') {
op.push(c);
} else if (c == ')') {
while (op.top() != '(') {
Do();
}
op.pop();
} else {
while (!op.empty() && g(op.top()) >= g(c)) {
Do();
}
op.push(c);
}
}
while (!op.empty()) {
Do();
}
return num.top();
}
}
using Calc::Ans;
int main() {
Init::init();
ex = clean();
string expression = "";
Train();
char c = ' ';
for (auto i: ex) {
c = to(i, c);
expression += c;
}
printf("%lld\n", Ans(expression));
return 0;
}
