2017微软秋季校园招聘在线编程笔试4——1402 : MS R

作者: codingXue | 来源:发表于2017-03-19 16:44 被阅读452次

Description
Given an image containing only two kinds of capital letters, 'M' and 'S', can you tell how many of each letter are there in the image? Note that the letters may be of different sizes and may be rotated.
Input
The first line contains two integers H and W, indicating the height and weight of the image. (1 <= H, W <= 500)
Then follows an H x W matrix indicating the image.
'.' indicates the pixel is empty and '#' indicates the pixel is part of a letter.
It is guaranteed that:

The letters are actually in Microsoft Yahei font.
Each letter consists of at least 20 pixels.
Different letters are at least 2 pixels away from each other.

Output
Two integers, the number of 'M' letters and the number of 'S' letters.
Sample Input
（我把每个“.”后面都加了一个空格，为了排版好看，原input数据附在本文最后）
50 50
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #. . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . ###. . . . . . . . . . ##. . . . . . .
. . . . . . . ##. . . . . . . . . . . . . . . . . . ##. ##. . . . . . . . #. . . . . . . . .
. . . . . . . ##. . . . . . . . . . . . . . . . . . #. . . . . . . . . . . ##. . . . . . . . .
. . . . . . ###. . . . . . . #. . . . . . . . . . #. . . . . . . . . . . ##. . . . . . . . .
. . . . . . ####. . . . . ###. . . . . . . . . ###. . . . . . . . . . ######. . . .
. . . . . . #. ##. . . . . ###. . . . . . . . . . ####. . . . . . . . . . . . . . #. . .
. . . . . . #. ##. . . . ####. . . . . . . . . . . . ##. . . . . . . . . . . . . . #. . .
. . . . . ##. . #. . . ##. #. . . . . . . . . . #. . . #. . . . . . . . . . . . . ##. . .
. . . . . ##. . #. . ##. ##. . . . . . . . . . #####. . . . . . . . . . . ##. . . . .
. . . . . #. . . #. ##. . ##. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . #. . . ###. . . #. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . #. . . ###. . . #. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . ##. . . ##. . . . . . . . . . . . . . . . . . . . . . ##. . . . . . . . . .
. . . . . . . . . . . . . . ##. . . . . ##. . . . . . . . . . . . . . ###. . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . ###. . . . . . . . . . . . ###. . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . ###. . . . . . . . . . . . . ##. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . ###. . . . . . . . . . . . . ##. . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . ###. . . . . . . . . . . . . . ##. . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . ###. . . . . . ###. . . . . . . ########. . . . . . .
. . . . . . . . . . . . . . . ###. . . . . #####. . . . . . . . ########. . . . . .
. . . . . . . . . . . . . . ###. . . ########. . . . . . . . . . . . . . . ##. . . . .
. . . . . . . . . . . . . ###. . #####. . ##. . . . . . . . . . . . . . . . ##. . . . .
. . . . . . . . . . . . ########. . . . ###. . . . . . . . . . . . . . . . ##. . . . .
. . . . . . . . . . . #######. . . . . . ##. . . . . ##. . . . . . . . . ###. . . . .
. . . . . . . . . . . . ###. . . . . . . . . ##. . . . ###. . . . . . . ####. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . ###. . . ###. . . . . . . ###. . . . . . . .
. . . . . . . #. . . . . . . . . . . . . . . ##. . . ###. . . . . . . . . . . . . . . . . . .
. . . . . ####. . . . . . . . . . . . . ###. . ###. . . . . . . . . . . . . . . . . . . .
. . . ######. . . . . . . . . . . . . ##. . ###. . . . . . . . . . . . . . . . . . . . .
. . ####. . . . . . . . . . . . . . . . ######. . . . . . . . . . . . . . . . . . . . . .
. . ###. . . . . . . . . . . . . . . . ######. . . . . . . . . . . . . . . . . . . . . . .
. ###. . . . . . . . . . . . . . . . . #####. . . . . . . ##. . . . . . . . . . . . . . .
. ###. . . . . . . . . . . . . . . . #####. . . . . . . . ######. . . . . . . . . . .
. ###. . . . . . . . . . . . . . . . . ###. . . . . . . . . ##########. . . . . . .
. . ##########. . . . . . . . . . . . . . . . . . . . . . . ##. . . ####. . . . . .
. . ############. . . . . . . . . . . . . . . . . . . . . . ##. . . . . . . . . . . .
. . . . ###########. . . . . . . . . . . . . . . . . . . . . . ###. . . . . . . . . .
. . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . . . . . . . . ###. . . . . . . . .
. . . . . . . . . . . . . ###. . . . . . . . . . . . . . . . . . . . . . . ###. . . . . . . .
. . . . . . . . . . . . . ###. . . . . . . . . . . . . . . . . . . #######. . . . . . . .
. . . . . . . . . . . . . ##. . . . . . . . . . . . . . . . ########. . . . . . . . . . .
. . . . . . . . . . . . ###. . . . . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . ####. . . . . . . . . . . . . . . . . . ######. . . . . . . . . . . .
. . . . . . . ######. . . . . . . . . . . . . . . . . . . . . . ######. . . . . . . . .
. . . . . . . ###. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ##. . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sample Output
3 4

思路分析
一看到这道题我是懵逼的。图像题？难道要用模式识别的方法吗？基本一点思路都没有。
我参考了yyblues的博客。
分析题意可以发现，图像中仅存在M和S两种字母，因此只要想办法区分这两种字母即可！并不需要用高大上的图像处理、模式识别方法。
具体的区分方法是：

从上到下、从左到右遍历二维数组，在接触到一个图像点时，从此点开始bfs，找到M/S的一个端点p₁（端点即为bfs时访问的最后一个点！）；
从p₁开始第二次bfs，找到M/S的第二个端点p₂；
在上面bfs的过程中，记录图像横纵坐标的最小值，因此可以得到一个将M/S框起来的矩形r；
取两个标志点：1) p₁和p₂的中点m，M和S的m点位置有很大差异，M的m点在下边沿中间，而S的m点在图形中心；2) 矩形r的中心c。如果字母是S，那么r和m的位置将很接近，如果为M，那么该距离相对会大一些。
设p₁与p₂的距离为dist₁，m与c的距离为dist₂，若dist₂/dist₁ < 0.4，则认为该字母是S，否则认为该字母是M。

这道题很有启发：不要一上来就把题想得太难，可能只需要很intuitive的方法就能解决！

AC代码

#include <iostream>
#include <queue>
#include <set>
#include <cmath>

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<point> q;
    set<point> 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));
}

原input数据
50 50
..................................................
..................................................
..........................................#.......
............................###..........##.......
.......##..................##.##........#.........
.......##..................#...........##.........
......###.......#..........#...........##.........
......####.....###.........###..........######....
......#.##.....###..........####..............#...
......#.##....####............##..............#...
.....##..#...##.#..........#...#.............##...
.....##..#..##.##..........#####...........##.....
.....#...#.##..##.................................
.....#...###...#..................................
.....#...###...#..................................
.........##...##......................##..........
..............##.....##..............###..........
....................###............###............
...................###.............##.............
..................###.............##..............
.................###..............##..............
................###......###.......########.......
...............###.....#####........########......
..............###...########...............##.....
.............###..#####..##................##.....
............########....###................##.....
...........#######......##.....##.........###.....
............###.........##....###.......####......
.......................###...###.......###........
.......#...............##...###...................
.....####.............###..###....................
...######.............##..###.....................
..####................######......................
..###................######.......................
.###.................#####.......##...............
.###................#####........######...........
.###.................###.........##########.......
..##########.......................##...####......
..############......................##............
....###########......................###..........
.............##.......................###.........
.............###.......................###........
.............###...................#######........
.............##................########...........
............###................####...............
..........####..................######............
.......######......................######.........
.......###.............................##.........
..................................................
..................................................

2017微软秋季校园招聘在线编程笔试4——1402 : MS R

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读