MS Recognition

• 描述

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.

• 输入

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:

1. The letters are actually in Microsoft Yahei font.

2. Each letter consists of at least 20 pixels.

3. Different letters are at least 2 pixels away from each other.

• 输出

Two integers, the number of 'M' letters and the number of 'S' letters.

• 样例输入

50 50
..................................................
..................................................
..........................................#.......
............................###..........##.......
.......##..................##.##........#.........
.......##..................#...........##.........
......###.......#..........#...........##.........
......####.....###.........###..........######....
......#.##.....###..........####..............#...
......#.##....####............##..............#...
.....##..#...##.#..........#...#.............##...
.....##..#..##.##..........#####...........##.....
.....#...#.##..##.................................
.....#...###...#..................................
.....#...###...#..................................
.........##...##......................##..........
..............##.....##..............###..........
....................###............###............
...................###.............##.............
..................###.............##..............
.................###..............##..............
................###......###.......########.......
...............###.....#####........########......
..............###...########...............##.....
.............###..#####..##................##.....
............########....###................##.....
...........#######......##.....##.........###.....
............###.........##....###.......####......
.......................###...###.......###........
.......#...............##...###...................
.....####.............###..###....................
...######.............##..###.....................
..####................######......................
..###................######.......................
.###.................#####.......##...............
.###................#####........######...........
.###.................###.........##########.......
..##########.......................##...####......
..############......................##............
....###########......................###..........
.............##.......................###.........
.............###.......................###........
.............###...................#######........
.............##................########...........
............###................####...............
..........####..................######............
.......######......................######.........
.......###.............................##.........
..................................................
..................................................

• 样例输出
  3 4

#include <iostream>
using namespace std;
#include <cmath>
#include <queue>
#include <set>

struct point {
    int x;
    int y;
    point() {}
    point(int _x, int _y) {
        x = _x;
        y = _y;
    }
    bool operator< (const point &p) const {
        if (p.x > x) return true;
        else if (p.x == x) return p.y > y;
        else return false;
    }
    bool operator== (const 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);
double dist(point& p1, point& p2);

int h, w;
char visible[501][501];
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) {
                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 center = point((min_x + max_x) / 2, (min_y + max_y) / 2);
                point middle = point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
                double dist1 = dist(p1, p2);
                double dist2 = dist(middle, center);
                if (dist2 / dist1 < 0.4) s++;
                else m++;
            }
        }
    }
    cout << m << ' ' << s;
    system("pause");
    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 },{ 0, 1 },{ 0, -1 },{ -1, 0 },{ -1, 1 },{ -1, -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;
                min_y = y < min_y ? y : min_y;
                max_x = x > max_x ? x : max_x;
                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));
}