本题是微软某场笔试的最后一题。由于能做出前3题基本就稳进面试，所以最后一题故意放了一道比较开放的题目，没有什么一定的标准算法。
基本的思路当然是分析M和S哪些统计量会相差比较大，从而足以当作区分的标准。
不过考虑到笔试时间有限，还需要衡量一下写代码的时间，太复杂的方法可能来不及写完代码。
标程使用的方法是，对于每个字母找到笔画的起点和终点。(即下图红圈圈中的像素点，只要起点和终点不偏离圈太远就可以。)
之后考虑连接起点和终点的连线。对于M来说，绝大多数像素点都在连线的同一侧；而对S来说，连线两侧的像素点数量大致相等。
找起点和终点可以用2遍BFS的方法：从字母中随便选取一点P，找距离P最远的点A，再找距离A最远的点B。将A和B当作起点和终点。
判断在连线哪一侧，是一个基本的计算几何问题，可以用向量叉积判断。
当然网上还有很多同学分享 其他的方法，大家也可以参考。
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)); }
