hiho一下第203周《MS Recognition》题目分析

5
0

《MS Recognition》题目分析

本题是微软某场笔试的最后一题。由于能做出前3题基本就稳进面试,所以最后一题故意放了一道比较开放的题目,没有什么一定的标准算法。

基本的思路当然是分析M和S哪些统计量会相差比较大,从而足以当作区分的标准。

不过考虑到笔试时间有限,还需要衡量一下写代码的时间,太复杂的方法可能来不及写完代码。

标程使用的方法是,对于每个字母找到笔画的起点和终点。(即下图红圈圈中的像素点,只要起点和终点不偏离圈太远就可以。)

之后考虑连接起点和终点的连线。对于M来说,绝大多数像素点都在连线的同一侧;而对S来说,连线两侧的像素点数量大致相等。

找起点和终点可以用2遍BFS的方法:从字母中随便选取一点P,找距离P最远的点A,再找距离A最远的点B。将A和B当作起点和终点。

判断在连线哪一侧,是一个基本的计算几何问题,可以用向量叉积判断。

当然网上还有很多同学分享 其他的方法,大家也可以参考。

2 answer(s)

0

这题真是一脸蒙蔽。。。

0

include

include

include

include

using namespace std;

struct point { int x; int y; point() {} point(int _x, int _y) { x = _x; y = _y; } bool operator< (point p) const { if (p.x < x) return true; else if (p.x == x) return p.y < y; else return false; } bool operator== (point p) const { return (x == p.x && y == p.y); } };

point dfs(point head, int& min_x, int& min_y, int& max_x, int& max_y); point dfs(point head); double dist(point& p1, point& p2);

int h, w; char visible[501][501] = { 0 }; char image[501][501];

int main() { int m = 0; int s = 0; cin >> h >> w; for (int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { cin >> image[i][j]; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (image[i][j] == '.' || visible[i][j] == 1) continue; int min_x = i, min_y = j, max_x = i, max_y = j; point node = point{ i, j }; point p1 = dfs(node, min_x, min_y, max_x, max_y); point p2 = dfs(p1, min_x, min_y, max_x, max_y); point middle = point{ (p1.x + p2.x) / 2, (p1.y + p2.y) / 2 }; point center = point{ (min_x + max_x) / 2, (min_y + max_y) / 2 }; double dist1 = dist(p1, p2); double dist2 = dist(middle, center); if (dist2 / dist1 < 0.4) s++; else m++; } } cout << m << ' ' << s; return 0; }

point dfs(point head, int& min_x, int& min_y, int& max_x, int& max_y) { int move[8][2] = { {1, 0}, {1, 1}, {1, -1}, {-1, 0}, {-1, 1}, {-1, -1}, {0, 1}, {0, -1} }; queue q; set s; q.push(head); s.insert(head); visible[head.x][head.y] = 1; point tmp; while (!q.empty()) { tmp = q.front(); q.pop(); for (int i = 0; i < 8; i++) { int x = tmp.x + move[i][0]; int y = tmp.y + move[i][1]; point node = point{ x, y }; if (x >= 0 && x < h && y >= 0 && y < w && image[x][y] == '#' && s.count(node) == 0) { q.push(node); s.insert(node); visible[x][y] = 1; min_x = x < min_x ? x : min_x; max_x = x > max_x ? x : max_x; min_y = y < min_y ? y : min_y; max_y = y > max_y ? y : max_y; } } } return tmp; }

double dist(point& p1, point& p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); }

write answer 切换为英文 切换为中文


转发分享