题解 AT678
经过了一周的努力后，终于把这题过了......
题意描述：
给你一张有数字和字符的图片，计算其表达式的值。
分析：
对于这道题来说，大体可以分为2个步骤:
其中表达式求值的部分可参考P1175（表达式的转换），将中缀表达式转为后缀表达式求值即可。
但最重要，也是最难以解决的部分，就是识别表达式的部分，应该怎么做呢？
首先，为了减少噪点的干扰，需要对图片进行降噪处理，这里，我采用了一种叫众数滤波器的降噪方法，这里展示的是对52号点的处理结果：
可以看到，效果相当显著。具体的代码实现也比较简单：
//对图片进行降噪处理
Image reducenoice(const Image& img)
{
Image tmp(img); //对img进行复制
auto valid = [&](int x, int y) {return x >= 0 and x < img.sx and y >= 0 and y < img.sy; }; //判定访问是否越界
int dx[] = { 0, 1, 1, 0, -1, -1, -1, 0, 1 };
int dy[] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 }; //创建遍历列表
for (int x = 0; x < img.sx; x++) {
for (int y = 0; y < img.sy; y++) { //对每个x, y进行循环
int cnt1 = 0, cnt2 = 0; //cnt1为周围1圈黑点数量，cnt2为周围1圈点的数量
for (int k = 0; k < 9; k++) { //遍历周围的点
int nx = x + dx[k], ny = y + dy[k];
if (valid(nx, ny))
cnt2++, cnt1 += img[nx][ny];
}
tmp[x][y] = (cnt1 * 2 > cnt2); //判定周围黑点数量是否比白点多，若是则将此处涂黑
}
}
return tmp;
}（其中Image是我为了方便操作图片而创建的类）
对整张图片进行降噪后，我们就可以准确地将各个字符从图片中按顺序分离出来了。因为题目保证了：
- 对于横向的位置，对于任意相邻的字符，它们之间会有
10 个像素的空白。
所以我们可以将图片逐列从上往下扫，来按顺序得到不同的字符。
这一部分的代码实现：
//将大于minsize大小的联通块分离出来
vector<Image> split(Image img, int minsize = 15)
{
vector<Image> res;
queue<pair<int, int>> q; //存储连通块中的黑点
int minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN;
auto init = [&]() {minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN; }; //初始化变量
auto valid = [&](int x, int y) { return x >= 0 and x < img.sx and y >= 0 and y < img.sy; }; //判定访问是否越界
auto bfs = [&](int x, int y) { //将当前连通块中所有黑点全部加入到队列q中
queue<pair<int, int>> q1;
int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
q1.push({ x, y }); q.push(q1.back());
chkmax(maxx, x), chkmax(maxy, y), chkmin(minx, x), chkmin(miny, y);
img[x][y] = 0;
while (!q1.empty()) {
auto h = q1.front();
int x = h.first, y = h.second;
q1.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny) and img[nx][ny]) {
q1.push({ nx, ny }); q.push(q1.back());
img[nx][ny] = 0;
chkmax(maxx, nx), chkmax(maxy, ny), chkmin(minx, nx), chkmin(miny, ny);
}
}
}
};
for (int j = 0; j < img.sy; j++) {
for (int i = 0; i < img.sx; i++) { //遍历整张图，注意变量枚举顺序
if (img[i][j]) { //如果此处存在黑点
init();
bfs(i, j); //得到与它相连的连通块
if (q.size() >= minsize) { //这里的判断是防止有些噪点未被处理干净，被当为单个字符分离出去
Image tmpimg(maxx - minx + 1, maxy - miny + 1, img.conv1, img.conv2); //依据大小构建子图
while (!q.empty()) {
auto p = q.front(); q.pop();
int x = p.first, y = p.second;
tmpimg[x - minx][y - miny] = 1; //将队列里的黑点放到子图的相应位置
}
res.push_back(tmpimg); //将子图放到列表里面
}
while (!q.empty()) q.pop();
}
}
}
return res;
}剩下来的，就是单个字符的识别过程了。到了这里，可能会束手无策，但是题面又一次给了我们重要的提示:
输入：
t \vdots 其中，
t 为非负整数，表示此为第t 组数据；所有以下数据按以下步骤生成：
\cdots 数据范围：
- 对于
0 \le t < 30 的数据:\vdots - 对于
30 \le t < 90 的数据:\vdots - 对于
90 \le t \le 140 的数据:\vdots
这说明什么？对于出现的所有字符，它都是通过确定的变换方式，通过不同的参数变换而来的。根据题意，可以写出变换部分的代码：
Image balance(const Image& img)
{
Image res(65, 38);
int sumx = 0, sumy = 0, sumc = 0;
for (int i = 0; i < img.sx; i++)
{
for (int j = 0; j < img.sy; j++)
{
if (img[i][j])
{
sumx += i, sumy += j, sumc++;
}
}
}
int cx = (2 * sumx + sumc) / (2 * sumc), cy = (2 * sumy + sumc) / (2 * sumc); //确定中心位置
int px = 32 - cx, py = 19 - cy; //确定偏移量
res = cover(res, img, px, py); //进行平移
return res;
}
auto trans = [&](const Image& img, double M, double Mx, double My, double R, double Sx, double Sy)
{
auto valid = [=](int x, int y) { return x >= 0 and x < 65 and y >= 0 and y < 38; }; //判断是否越界
Image imgans(65, 38);
for (int i = 0; i < 65; i++)
{
for (int j = 0; j < 38; j++)
{
if (img[i][j])
{
double y = i + 0.5 - 32.5, x = j + 0.5 - 19; //先对像素点进行平移，方便后面的旋转,扭曲操作
x *= M * Mx, y *= M * My; //进行横向/纵向伸缩变换
double nx = x * cos(torad(R)) - y * sin(torad(R)), ny = x * sin(torad(R)) + y * cos(torad(R)); //进行旋转变换
x = nx + Sy * ny, y = ny + Sx * nx; //进行扭曲变换
int X = int(round(y + 32.5 - 0.5)), Y = int(round(x + 19 - 0.5)); //最终的X, Y坐标
if (valid(X, Y))
{
imgans[X][Y] = 1;
}
}
}
}
return balance(reducenoice(imgans)); //对变换后的图像降噪后再摆正位置
};有了变换函数了后，我们就可以在题目给定的参数范围内，随机生成多张图像，来应对可能出现的多种情况。这里是初始化函数的实现：
void init(int t)
{
for (int i = 0; i < 16; i++)
{
Signset[i] = cover(Image(65, 38), Signset[i], Signpos[i][0], Signpos[i][1]); //这里我为了减少代码长度，只截取了各个字符的黑色区域，保存了它们的左上角坐标，这一步做的就是还原他们原来所在的位置
}
double Mmin = 0.9, Mmax = 1, Rmin, Rmax, Smin, Smax;
if (0 <= t and t < 30)
{
Rmin = -2, Rmax = 2, Smin = Smax = 0;
}
else if (30 <= t and t < 90)
{
Rmin = -10, Rmax = 10, Smin = -0.1, Smax = 0.1;
}
else
{
Rmin = -15, Rmax = 15, Smin = -0.1, Smax = 0.1;
}
uniform_real_distribution M(Mmin, Mmax), R(Rmin, Rmax), S(Smin, Smax); //初始化随机数生成器
default_random_engine gen(time(NULL)); //初始化随机数生成器
auto trans = [&](const Image& img, double M, double Mx, double My, double R, double Sx, double Sy)
{
auto valid = [=](int x, int y) { return x >= 0 and x < 65 and y >= 0 and y < 38; }; //判断是否越界
Image imgans(65, 38);
for (int i = 0; i < 65; i++)
{
for (int j = 0; j < 38; j++)
{
if (img[i][j])
{
double y = i + 0.5 - 32.5, x = j + 0.5 - 19; //先对像素点进行平移，方便后面的旋转,扭曲操作
x *= M * Mx, y *= M * My; //进行横向/纵向伸缩变换
double nx = x * cos(torad(R)) - y * sin(torad(R)), ny = x * sin(torad(R)) + y * cos(torad(R)); //进行旋转变换
x = nx + Sy * ny, y = ny + Sx * nx; //进行扭曲变换
int X = int(round(y + 32.5 - 0.5)), Y = int(round(x + 19 - 0.5)); //最终的X, Y坐标
if (valid(X, Y))
{
imgans[X][Y] = 1;
}
}
}
}
return balance(reducenoice(imgans)); //对变换后的图像降噪后再摆正位置
};
for (int i = 0; i < 16; i++) //枚举每个字符
{
for (int j = 0; j < maxitertime; j++) //在参数范围内随机生成至多maxitertime张图像，这里的数字为75
{
double _M = M(gen), _Mx = M(gen), _My = M(gen), _R = R(gen), _Sx = S(gen), _Sy = S(gen); //获取随机数
randomset[i][j] = trans(Signset[i], _M, _Mx, _My, _R, _Sx, _Sy); //生成随机图像
}
}
}对单字符的匹配也能顺便写出来了：
const char* convtable = "0123456789()+-*/"; //字符转换表
double operator==(const Image& img1, const Image& img2)
{
int bx = img2.sx, by = img2.sy;
double cnt = 0;
for (int i = 0; i < img1.sx; i++)
{
for (int j = 0; j < img1.sy; j++)
{
cnt += (img2[i][j] == img1[i][j]) ? 1 : 0;
}
}
return (cnt / double(img1.sx * img1.sy));
}
char recognize(const Image& img)
{
double rate = 0;
int idx = -1;
Image imgtmp = balance(img); //调整img的位置
#ifdef debug
cout << "Balancing the input :\n" << imgtmp << endl;
#endif // debug
for (int i = 0; i < maxitertime; i++)
{
for (int j = 0; j < 16; j++)
{
double r = (imgtmp == randomset[j][i]); //比较相似程度
if (r > rate) //如果匹配度最大
{
rate = r; //记录匹配度
idx = j; //记录编号
}
}
}
return convtable[idx]; //返回对应的字符
}最后，位于主函数的的计算部分也能写出来了：
int main()
{
string tmp1, tmp2;
cin >> t >> n >> m;
init(t); //根据数据编号初始化
while (cin >> tmp2)
{
tmp1 += tmp2 + ' ';
}
test = Image(tmp1); //从字符串构造图像
test = reducenoice(test); //对图像进行降噪
//cout << test << endl << endl;
test2 = split(test); //分离单个字符
tmp2.clear();
for (const auto& i : test2)
{
//cout << i << endl << endl;
tmp2 += recognize(i); //分别对列表中的字符逐一识别，并加到字符串中
}
cout << calc(tmp2) << endl; //最后调用计算函数，完成计算（一定要加换行符啊！）
}这道题就这么结束了
code: (其中有很多我写代码时用来调试的无用代码...）
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#define runmode 3
//#define debug 1
using namespace std;
const double pi = 3.141592653589793;
const int maxitertime = 75;
#define Range(x) (x).begin(), (x).end()
template <typename T>
void chkmax(T& x, T y) { x = max(x, y); }
template <typename T>
void chkmin(T& x, T y) { x = min(x, y); }
double torad(double x) { return x / 180.0 * pi; }
const function<int(char)> conv1 = [](const char c) {return c == '.' ? 0 : 1; };
const function<char(int)> conv2 = [](const int c) {return c ? '#' : '.'; };
const char* convtable = "0123456789()+-*/"; //字符转换表
//ofstream out("data.out");
struct Image
{
vector<vector<int>> raw;
function<int(char)> conv1 = [](const char c) {return int(c); };
function<char(int)> conv2 = [](const int c) {return char(c); };
Image() = default;
int sx, sy;
Image(int sx, int sy, function<int(char)> c1 = ::conv1, function<char(int)> c2 = ::conv2) :sx(sx), sy(sy), conv1(c1), conv2(c2) {
raw.resize(sx);
fill(Range(raw), vector<int>(sy));
}
auto& operator[](int x) { return raw[x]; }
const auto& operator[](int x) const { return raw[x]; }
//从字符串构造图片
Image(const string& a, function<int(char)> c1 = ::conv1, function<char(int)> c2 = ::conv2) : conv1(c1), conv2(c2) {
sx = sy = 0;
stringstream s1;
string s2;
s1 << a;
while (s1 >> s2) {
vector<int> s3;
for (const auto i : s2) {
s3.push_back(conv1(i));
}
raw.push_back(s3);
sx++;
chkmax(sy, int(s3.size()));
}
}
Image(const char* a, function<int(char)> c1 = ::conv1, function<char(int)> c2 = ::conv2) : conv1(c1), conv2(c2) {
sx = sy = 0;
stringstream s1;
string s2;
s1 << a;
while (s1 >> s2) {
vector<int> s3;
for (const auto i : s2) {
s3.push_back(conv1(i));
}
raw.push_back(s3);
sx++;
chkmax(sy, int(s3.size()));
}
}
friend int colorcount(const Image& img)
{
int cnt = 0;
for (const auto& i : img.raw)
{
for (const auto& j : i)
{
cnt += j;
}
}
return cnt;
}
Image subImage(int sx, int sy, int ex, int ey) const
{
Image res(ex - sx + 1, ey - sy + 1);
for (int i = sx; i <= ex; i++)
{
for (int j = sy; j <= ey; j++)
{
res[i - sx][j - sy] = raw[i][j];
}
}
return res;
}
tuple<int, int, int, int> getminmaxrange() const
{
int minx = INT_MAX, maxx = 0, miny = INT_MAX, maxy = 0;
for (int i = 0; i < sx; i++)
{
for (int j = 0; j < sy; j++)
{
if (raw[i][j])
{
chkmax(maxx, i);
chkmin(minx, i);
chkmax(maxy, j);
chkmin(miny, j);
}
}
}
return { minx, miny, maxx, maxy };
}
bitset<65 * 38> tobitset() const
{
bitset<65 * 38> res;
assert(sx == 65 and sy == 38);
for (int i = 0; i < 65; i++)
{
for (int j = 0; j < 38; j++)
{
res[i * 38 + j] = raw[i][j];
}
}
return res;
}
void resize(int nx, int ny){
sx = nx, sy = ny;
raw.resize(ny);
for_each(Range(raw), [=](auto& i) { i.resize(nx); });
}
friend ostream& operator<<(ostream& out, const Image& img) {
for (const auto& i : img.raw) {
for (const auto j : i)
cout << img.conv2(j);
cout << endl;
}
return out;
}
};
#pragma region data
vector<Image> Signset{ //各个字符对应的图像
R"(
...........########...........
.........############.........
.......################.......
......##################......
.....####################.....
....######################....
...########################...
...##########....##########...
..#########........#########..
..########..........########..
.#########..........#########.
.########............########.
.########............########.
.########............########.
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
.########............########.
.########............########.
.########............########.
.#########..........#########.
..########..........########..
..#########........#########..
...##########....##########...
...########################...
....######################....
.....####################.....
......##################......
.......################.......
.........############.........
...........########...........
)",
R"(
.............####..........
...........#######.........
........##########.........
.....#############.........
..################.........
.#################.........
.#################.........
.#################.........
.#################.........
..######..########.........
..###.....########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
.##########################
###########################
###########################
###########################
###########################
.##########################
)",
R"(
.........#########..........
......##############........
...###################......
..#####################.....
.#######################....
.#######################....
.########################...
.#########......#########...
.#######.........#########..
.#######..........########..
.#######..........########..
.#######..........########..
.#######..........########..
..######..........########..
.................#########..
.................########...
................#########...
...............##########...
..............##########....
.............###########....
............###########.....
...........###########......
..........###########.......
.........###########........
........###########.........
.......###########..........
......###########.....#####.
.....###########.....#######
....###########......#######
...###########.......#######
..###########........#######
.###########.........#######
############################
############################
############################
############################
############################
.###########################
)",
R"(
.........##########.........
.....################.......
...####################.....
..######################....
..#######################...
..########################..
..########################..
..########.......##########.
..#######.........#########.
..#######..........########.
..#######..........########.
...######..........########.
...................########.
...................########.
..................########..
.................#########..
..........###############...
.........###############....
.........##############.....
.........###############....
.........################...
..........################..
.................##########.
...................########.
...................#########
....................########
....................########
....................########
....................########
...................#########
..###.............##########
.########........##########.
.##########################.
.#########################..
##########################..
.########################...
.######################.....
....#################.......
.......###########..........
)",
R"(
.................#####........
................#######.......
...............########.......
..............#########.......
.............##########.......
............###########.......
............###########.......
...........############.......
..........#############.......
.........##############.......
........###############.......
.......################.......
.......########.#######.......
......########..#######.......
.....########...#######.......
....########....#######.......
...#########....#######.......
...########.....#######.......
..########......#######.......
.########.......#######.......
##############################
##############################
##############################
##############################
##############################
##############################
...............########.......
...............########.......
...............########.......
...............########.......
...............########.......
...............########.......
.........####################.
........#####################.
........#####################.
........#####################.
........#####################.
.........####################.
)",
R"(
...######################...
...#######################..
...#######################..
...#######################..
...#######################..
...######################...
...#######..................
...#######..................
...#######..................
...#######..................
...#######..................
...#######..................
..########..########........
..####################......
..######################....
..#######################...
..########################..
..########################..
..#########################.
..########.......##########.
.....##...........#########.
...................#########
....................########
....................########
....................########
....................########
....................########
....................########
...#...............#########
..####............#########.
.########.......###########.
.##########################.
.#########################..
#########################...
.#######################....
..#####################.....
....#################.......
........##########..........
)",
R"(
....................######...
...............###########...
............###############..
..........#################..
........###################..
.......####################..
......####################...
.....################........
....############.............
...###########...............
...#########.................
..#########..................
..########...................
.########....................
.########....................
.#######....########.........
.#######..#############......
#########################....
##########################...
###########################..
###########################..
############......##########.
##########.........#########.
#########...........#########
########.............########
########.............########
########.............########
.#######.............########
.#######.............########
.########...........#########
.#########.........#########.
..##########.....###########.
...#########################.
...########################..
....######################...
.....####################....
......##################.....
........##############.......
...........########..........
)",
R"(
###########################.
############################
############################
############################
############################
###########################.
#######...........#########.
#######...........#########.
#######..........#########..
#######..........#########..
#######..........########...
#######.........#########...
#######.........########....
#######........#########....
.#####.........#########....
...............########.....
..............#########.....
..............########......
.............#########......
.............########.......
............#########.......
............#########.......
............########........
...........#########........
...........########.........
..........#########.........
..........########..........
..........########..........
.........########...........
.........########...........
........#########...........
........########............
........########............
.......########.............
.......########.............
.......#######..............
.......#######..............
.........#####..............
)",
R"(
..........#########.........
........#############.......
......#################.....
.....###################....
....#####################...
...#######################..
...#######################..
...#########.....#########..
..#########.......#########.
..########.........########.
..########.........########.
..########.........########.
..########.........########.
..########.........########.
...########.......########..
...#########.....#########..
....#####################...
.....###################....
......#################.....
......#################.....
....#####################...
...#######################..
..#########......##########.
.########..........########.
.########..........#########
########............########
########............########
########............########
########............########
#########..........#########
#########..........#########
.##########......##########.
.##########################.
..########################..
..########################..
...######################...
....####################....
......################......
.........##########.........
)",
R"(
.........#########..........
.......#############........
.....#################......
....###################.....
...#####################....
..#######################...
.########################...
.##########......#########..
.#########........#########.
#########..........########.
########............#######.
########............#######.
########............########
########............########
########............########
#########..........#########
.########.........##########
.##########......###########
..##########################
..##########################
...#########################
....########################
......############..########
........########....#######.
....................#######.
...................########.
...................########.
..................########..
.................#########..
...............##########...
.............############...
.........###############....
....###################.....
...###################......
...##################.......
...################.........
...##############...........
...############.............
....######..................
)",
R"(
...............####..
..............######.
............########.
...........##########
..........###########
.........############
........############.
.......###########...
......###########....
.....###########.....
.....##########......
....##########.......
....#########........
...#########.........
...########..........
..#########..........
..########...........
.#########...........
.########............
.########............
.########............
#########............
########.............
########.............
########.............
########.............
########.............
########.............
########.............
########.............
########.............
########.............
.########............
.########............
.########............
.#########...........
..########...........
..#########..........
..#########..........
...#########.........
...##########........
....#########........
.....#########.......
.....##########......
......###########....
.......###########...
........###########..
.........############
..........###########
...........##########
............#########
.............#######.
...............####..
.................#...
)",
R"(
..####...............
.######..............
#########............
##########...........
###########..........
############.........
.############........
...###########.......
....###########......
.....##########......
......##########.....
.......##########....
........#########....
.........#########...
..........########...
..........#########..
...........########..
...........#########.
............########.
............########.
............########.
............#########
.............########
.............########
.............########
.............########
.............########
.............########
.............########
.............########
.............########
.............########
............########.
............########.
............########.
...........#########.
...........########..
..........#########..
..........#########..
.........#########...
........##########...
.......##########....
.......#########.....
.....###########.....
....###########......
...###########.......
..###########........
############.........
###########..........
##########...........
#########............
.#######.............
..####...............
...#.................
)",
R"(
...........#####...........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
###########################
###########################
###########################
###########################
###########################
###########################
###########################
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
...........#####...........
)",
R"(
.##########################.
############################
############################
############################
############################
############################
.###########################
)",
R"(
...........####...........
..........######..........
..........#######.........
.........########.........
.........########.........
..........#######.........
..........######..........
.#####....######.....####.
.######...######...#######
#########..#####.#########
###############.##########
##########################
##########################
.########################.
......##############......
.........########.........
........###########.......
.......#############......
.....########.#######.....
....########..########....
....########..#########...
...########....########...
...########....########...
....#######.....#######...
.....#####......######....
......###.........##......
)",
R"(
......................####..
......................######
.....................#######
.....................#######
....................########
....................#######.
...................########.
...................#######..
..................########..
..................#######...
.................########...
.................#######....
................########....
................########....
................#######.....
...............########.....
...............#######......
..............########......
..............#######.......
.............########.......
.............#######........
............########........
............#######.........
...........########.........
...........#######..........
..........########..........
..........#######...........
..........#######...........
.........########...........
.........#######............
........########............
........#######.............
.......########.............
.......#######..............
......########..............
......#######...............
.....########...............
.....#######................
....########................
....#######.................
...########.................
...########.................
...#######..................
..########..................
..#######...................
.########...................
.#######....................
########....................
#######.....................
.######.....................
..#####.....................
)",
};
int Signpos[16][2] = { //字符在原来尺寸下的左上角的位置
{ 7, 4 },
{ 7, 6 },
{ 7, 5 },
{ 7, 5 },
{ 7, 4 },
{ 8, 5 },
{ 7, 5 },
{ 8, 6 },
{ 7, 5 },
{ 7, 5 },
{ 4, 8 },
{ 4, 9 },
{ 13, 6 },
{ 23, 5 },
{ 7, 6 },
{ 3, 5 }
};
Image randomset[16][maxitertime];
#pragma endregion This is the image data
Image cover(const Image& img1, const Image& img2, int sx, int sy)
{
Image imgans(img1);
for (int i = max(0, -sx); i < min(img2.sx, img1.sx - sx); i++)
{
for (int j = max(0, -sy); j < min(img2.sy, img1.sy - sy); j++)
{
imgans[i + sx][j + sy] = img2[i][j];
}
}
return imgans;
}
//对图片进行降噪处理
Image reducenoice(const Image& img)
{
Image tmp(img); //对img进行复制
auto valid = [&](int x, int y) {return x >= 0 and x < img.sx and y >= 0 and y < img.sy; }; //判定访问是否越界
int dx[] = { 0, 1, 1, 0, -1, -1, -1, 0, 1 };
int dy[] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 }; //创建遍历列表
for (int x = 0; x < img.sx; x++) {
for (int y = 0; y < img.sy; y++) { //对每个x, y进行循环
int cnt1 = 0, cnt2 = 0; //cnt1为周围1圈黑点数量，cnt2为周围1圈点的数量
for (int k = 0; k < 9; k++) { //遍历周围的点
int nx = x + dx[k], ny = y + dy[k];
if (valid(nx, ny))
cnt2++, cnt1 += img[nx][ny];
}
tmp[x][y] = (cnt1 * 2 > cnt2); //判定周围黑点数量是否比白点多，若是则将此处涂黑
}
}
return tmp;
}
Image reducesize(const Image& img)
{
const auto& rng = img.getminmaxrange();
int minx, maxx, miny, maxy;
tie(minx, maxx, miny, maxy) = rng;
return img.subImage(minx, maxx, miny, maxy);
}
//将大于minsize大小的联通块分离出来
vector<Image> split(Image img, int minsize = 15)
{
vector<Image> res;
queue<pair<int, int>> q; //存储连通块中的黑点
int minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN;
auto init = [&]() {minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN; }; //初始化变量
auto valid = [&](int x, int y) { return x >= 0 and x < img.sx and y >= 0 and y < img.sy; }; //判定访问是否越界
auto bfs = [&](int x, int y) { //将当前连通块中所有黑点全部加入到队列q中
queue<pair<int, int>> q1;
int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
q1.push({ x, y }); q.push(q1.back());
chkmax(maxx, x), chkmax(maxy, y), chkmin(minx, x), chkmin(miny, y);
img[x][y] = 0;
while (!q1.empty()) {
auto h = q1.front();
int x = h.first, y = h.second;
q1.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny) and img[nx][ny]) {
q1.push({ nx, ny }); q.push(q1.back());
img[nx][ny] = 0;
chkmax(maxx, nx), chkmax(maxy, ny), chkmin(minx, nx), chkmin(miny, ny);
}
}
}
};
for (int j = 0; j < img.sy; j++) {
for (int i = 0; i < img.sx; i++) { //遍历整张图，注意变量枚举顺序
if (img[i][j]) { //如果此处存在黑点
init();
bfs(i, j); //得到与它相连的连通块
if (q.size() >= minsize) { //这里的判断是防止有些噪点未被处理干净，被当为单个字符分离出去
Image tmpimg(maxx - minx + 1, maxy - miny + 1, img.conv1, img.conv2); //依据大小构建子图
while (!q.empty()) {
auto p = q.front(); q.pop();
int x = p.first, y = p.second;
tmpimg[x - minx][y - miny] = 1; //将队列里的黑点放到子图的相应位置
}
res.push_back(tmpimg); //将子图放到列表里面
}
while (!q.empty()) q.pop();
}
}
}
return res;
}
//对图像进行线性拉伸变换
Image resize(const Image& img, int nx, int ny)
{
Image res(nx, ny);
/*vector<vector<double>> cnt;
for (int i = 1; i <= nx; i++)
cnt.push_back(vector<double>(ny));*/
auto valid = [=](int x, int y) { return x >= 0 and x < nx and y >= 0 and y < ny; };
double cx = double(nx) / img.sx, cy = double(ny) / img.sy;
if (cx < 1)
{
for (int i = 0; i < img.sx; i++)
{
if (cy < 1)
{
for (int j = 0; j < img.sy; j++)
{
if (img[i][j])
res[int(i * cx)][int(j * cy)] = 1;
}
}
else
{
for (int j = 0; j < ny; j++)
{
if (img[i][int(j / cy)])
res[int(i * cx)][j] = 1;
}
}
}
}
else
{
for (int i = 0; i < nx; i++)
{
if (cy < 1)
{
for (int j = 0; j < img.sy; j++)
{
if (img[int(i / cx)][j])
res[i][int(j * cy)] = 1;
}
}
else
{
for (int j = 0; j < ny; j++)
{
if (img[int(i / cx)][int(j / cy)])
res[i][j] = 1;
}
}
}
}
return res;
}
//对图像进行旋转变换
Image rotate(const Image& img, double angle)
{
angle = angle / 180 * pi;
double minx = 1e5, maxx = -1e5, miny = 1e5, maxy = -1e5;
vector<pair<double, double>> points;
auto singlerotate = [](pair<double, double> p, double angle)
{
double x = p.second, y = -p.first;
double nx = x * cos(angle) - y * sin(angle), ny = x * sin(angle) + y * cos(angle);
return pair<double, double>({ -ny, nx });
};
for (int i = 0; i < img.sx; i++)
{
for (int j = 0; j < img.sy; j++)
{
if (img[i][j])
{
points.push_back({ i, j });
}
}
}
for (auto& i : points)
{
i = singlerotate(i, angle);
chkmax(maxx, i.first);
chkmin(minx, i.first);
chkmax(maxy, i.second);
chkmin(miny, i.second);
}
Image res(int(maxx - minx + 1), int(maxy - miny + 1));
for (const auto& i : points)
{
int x = (i.first - minx), y = (i.second - miny);
res[x][y] = 1;
}
return res;
}
double operator==(const Image& img1, const Image& img2)
{
int bx = img2.sx, by = img2.sy;
double cnt = 0;
for (int i = 0; i < img1.sx; i++)
{
for (int j = 0; j < img1.sy; j++)
{
cnt += (img2[i][j] == img1[i][j]) ? 1 : 0;
}
}
return (cnt / double(img1.sx * img1.sy));
}
Image balance(const Image& img)
{
Image res(65, 38);
int sumx = 0, sumy = 0, sumc = 0;
for (int i = 0; i < img.sx; i++)
{
for (int j = 0; j < img.sy; j++)
{
if (img[i][j])
{
sumx += i, sumy += j, sumc++;
}
}
}
int cx = (2 * sumx + sumc) / (2 * sumc), cy = (2 * sumy + sumc) / (2 * sumc); //确定中心位置
int px = 32 - cx, py = 19 - cy; //确定偏移量
res = cover(res, img, px, py); //进行平移
return res;
}
char recognize(const Image& img)
{
double rate = 0;
int idx = -1;
Image imgtmp = balance(img); //调整img的位置
#ifdef debug
cout << "Balancing the input :\n" << imgtmp << endl;
#endif // debug
for (int i = 0; i < maxitertime; i++)
{
for (int j = 0; j < 16; j++)
{
double r = (imgtmp == randomset[j][i]); //比较相似程度
if (r > rate) //如果匹配度最大
{
rate = r; //记录匹配度
idx = j; //记录编号
}
}
}
return convtable[idx]; //返回对应的字符
}
int t, n, m;
Image test;
vector<Image> test2, signset;
int calc(const string& s)
{
vector<int> stk1;
vector<char> stk2;
int optnum = 0, isd = 0;
auto cal = [&](char c)
{
int rhs = stk1.back();
stk1.pop_back();
int lhs = stk1.back();
stk1.pop_back();
switch (c)
{
case '+':
stk1.push_back(lhs + rhs);
break;
case '-':
stk1.push_back(lhs - rhs);
break;
case '*':
stk1.push_back(lhs * rhs);
break;
case '/':
stk1.push_back(lhs / rhs);
break;
}
};
auto level = [](char c)
{
switch (c)
{
case '(':
return 0;
break;
case '+':
case '-':
return 1;
break;
case '*':
case '/':
return 2;
break;
}
return -1;
};
for (const auto c : s)
{
if (c >= '0' and c <= '9')
{
optnum = 10 * optnum + (c - 48);
isd = 1;
}
else
{
if (isd)
{
stk1.push_back(optnum);
isd = 0;
optnum = 0;
}
if (stk2.empty())
{
stk2.push_back(c);
}
else
{
switch (c)
{
case '(':
stk2.push_back(c);
break;
case ')':
while (stk2.back() != '(')
{
cal(stk2.back());
stk2.pop_back();
}
stk2.pop_back();
break;
default:
while (!stk2.empty() and level(c) <= level(stk2.back()))
{
cal(stk2.back());
stk2.pop_back();
}
stk2.push_back(c);
}
}
}
}
if (isdigit(s.back()))
{
stk1.push_back(optnum);
}
while (!stk2.empty())
{
cal(stk2.back());
stk2.pop_back();
}
return stk1.back();
}
void init(int t)
{
for (int i = 0; i < 16; i++)
{
Signset[i] = cover(Image(65, 38), Signset[i], Signpos[i][0], Signpos[i][1]); //这里我为了减少代码长度，只截取了各个字符的黑色区域，保存了它们的左上角坐标，这一步做的就是还原他们原来所在的位置
#ifdef debug
cout << "char " << convtable[i] << ":\n" << Signset[i] << endl;
#endif // debug
}
double Mmin = 0.9, Mmax = 1, Rmin, Rmax, Smin, Smax;
if (0 <= t and t < 30)
{
Rmin = -2, Rmax = 2, Smin = Smax = 0;
}
else if (30 <= t and t < 90)
{
Rmin = -10, Rmax = 10, Smin = -0.1, Smax = 0.1;
}
else
{
Rmin = -15, Rmax = 15, Smin = -0.1, Smax = 0.1;
}
uniform_real_distribution M(Mmin, Mmax), R(Rmin, Rmax), S(Smin, Smax); //初始化随机数生成器
default_random_engine gen(time(NULL)); //初始化随机数生成器
auto trans = [&](const Image& img, double M, double Mx, double My, double R, double Sx, double Sy)
{
auto valid = [=](int x, int y) { return x >= 0 and x < 65 and y >= 0 and y < 38; }; //判断是否越界
Image imgans(65, 38);
for (int i = 0; i < 65; i++)
{
for (int j = 0; j < 38; j++)
{
if (img[i][j])
{
double y = i + 0.5 - 32.5, x = j + 0.5 - 19; //先对像素点进行平移，方便后面的旋转,扭曲操作
x *= M * Mx, y *= M * My; //进行横向/纵向伸缩变换
double nx = x * cos(torad(R)) - y * sin(torad(R)), ny = x * sin(torad(R)) + y * cos(torad(R)); //进行旋转变换
x = nx + Sy * ny, y = ny + Sx * nx; //进行扭曲变换
int X = int(round(y + 32.5 - 0.5)), Y = int(round(x + 19 - 0.5)); //最终的X, Y坐标
if (valid(X, Y))
{
imgans[X][Y] = 1;
}
}
}
}
return balance(reducenoice(imgans)); //对变换后的图像降噪后再摆正位置
};
for (int i = 0; i < 16; i++) //枚举每个字符
{
#ifdef debug
cout << "Generating data from char " << convtable[i] << " :\n";
#endif // debug
for (int j = 0; j < maxitertime; j++) //在参数范围内随机生成至多maxitertime张图像，这里的数字为75
{
double _M = M(gen), _Mx = M(gen), _My = M(gen), _R = R(gen), _Sx = S(gen), _Sy = S(gen); //获取随机数
randomset[i][j] = trans(Signset[i], _M, _Mx, _My, _R, _Sx, _Sy); //生成随机图像
#ifdef debug
cout << "M = " << _M << ", Mx = " << _Mx << ", My = " << _My << ", R = " << _R << ", Sx = " << _Sx << ", Sy = " << _Sy << endl;
cout << randomset[i][j] << endl << endl;
#endif // debug
}
}
}
int main()
{
#if runmode == 1
ifstream in("font.txt");
freopen("data.out", "w", stdout);
cout << "vector<Image> Signset{\n";
for (int i = 0; i < 16; i++)
{
string tmp, tmp2;
for (int j = 1; j <= 65; j++)
{
in >> tmp2;
tmp += tmp2 + '\n';
}
auto img = Image(tmp);
signset.push_back(reducesize(img));
cout << "R\"(\n" << reducesize(img) << ")\", \n";
tie(Signpos[i][0], Signpos[i][1], ignore, ignore) = img.getminmaxrange();
}
cout << "};\n";
cout << "int Signpos[16][2] = \n{\n";
for (int i = 0; i < 16; i++)
{
cout << " { " << Signpos[i][0] << ", " << Signpos[i][1] << " },\n";
}
cout << "};\n";
#endif
#if runmode == 2
#ifndef ONLINE_JUDGE
freopen("data.out", "w", stdout);
#endif
init(10);
#endif
#if runmode == 3
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
string tmp1, tmp2;
cin >> t >> n >> m;
init(t); //根据数据编号初始化
while (cin >> tmp2)
{
tmp1 += tmp2 + ' ';
}
test = Image(tmp1); //从字符串构造图像
test = reducenoice(test); //对图像进行降噪
//cout << test << endl << endl;
test2 = split(test); //分离单个字符
tmp2.clear();
for (const auto& i : test2)
{
//cout << i << endl << endl;
tmp2 += recognize(i); //分别对列表中的字符逐一识别，并加到字符串中
}
#ifndef ONLINE_JUDGE
cout << tmp2 << endl << calc(tmp2);
#else
cout << calc(tmp2) << endl; //最后调用计算函数，完成计算（一定要加换行符啊！）
#endif
#endif
}
后记：
这道题的确是一道非常有挑战性的题目，我花费了将近一周，尝试了不同的方法，最终，在我代码自带的大常数下，以每点最高900ms的速度通过了此题。感谢之前为了A掉此题而不断尝试的人，同时感谢为我提供了一定思路的 @UIKIt 的题解，尽管我按照他的想法最终只拿了430pts。
这一题在洛谷上没有一份C++代码过题的历史，终于结束了。