题目链接：#1402 : MS Recognition

可惜当时代码没有写出来……感受不爱。刚才重新调试，应该可以 AC 了。

思路是找到 ‘M’ 和 'S' 的线划的端点。 如果这两个端点的【中点】和字符【包围盒的中心】比较接近，则为 'S'，否则为 'M'。

这是标记后的结果，两个端点和它们的中点标记了 '@'，可以看到 ‘M’ 和 'S' 有明显的区别：

..................................................
..................................................
..........................................X.......
............................XXX..........X@.......
.......XX..................XX.X@........X.........
.......XX..................X...........XX.........
......XXX.......X..........X...........XX.........
......XXXX.....XXX.........XX@..........XX@XXX....
......X.XX.....XXX..........XXXX..............X...
......X.XX....XXXX............XX..............X...
.....XX..X...XX.X..........X...X.............XX...
.....XX..X..XX.XX..........@XXXX...........@X.....
.....X...X.XX..XX.................................
.....X...XXX...X..................................
.....@...XXX...X..................................
.........@X...XX......................XX..........
..............@X.....X@..............XX@..........
....................XXX............XXX............
...................XXX.............XX.............
..................XXX.............XX..............
.................XXX..............XX..............
................XXX......XX@.......XXXXXXXX.......
...............XXX.....XXXXX........XXX@XXXX......
..............XXX...XXXXXXXX...............XX.....
.............XXX..XXXXX..XX................XX.....
............XXXXXXXX....XXX................XX.....
...........XXXXXXX......XX.....XX.........XXX.....
............XXX.........XX....XX@.......XXXX......
.......................XXX...XXX.......@XX........
.......X...............XX...XXX...................
.....XXX@.............XXX..XXX....................
...XXXXXX.............XX..XXX.....................
..XXXX................XXXXXX......................
..XXX................XXXXXX.......................
.XXX.................XXXXX.......XX...............
.XXX................XXXXX........XXXXXX...........
.XXX.................XXX.........XXXXXXXXXX.......
..XXXXXXXXXX.......................XX...XXX@......
..XXXXX@XXXXXX......................XX............
....XXXXXXXXXXX......................XXX..........
.............XX.......................XXX.........
.............XXX.......................XXX........
.............XXX...................XXXXXX@........
.............XX................XXXXXXXX...........
............XXX................XXXX...............
..........XXXX..................XXXXXX............
.......@XXXXX......................XXXXXX.........
.......XXX.............................X@.........
..................................................
..................................................
3 4

代码：

#include <queue>
#include <cstdio>
#include <unordered_set>

using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define MAXN 501
#define DOT '#'
#define CLR 'X'
#define BEG '@'
#define END '@'
#define MID '@'

int H, W;
char pic[MAXN][MAXN];
const int dx[] = { 1,-1, 0, 0, 1, 1,-1,-1};
const int dy[] = { 0, 0, 1,-1, 1,-1, 1,-1};

struct Point {
    int x, y;
    Point( int x = 0, int y = 0 ) : x(x), y(y) { }
    bool valid() const {
        return 0 <= x && x < H && 0 <= y && y < W;
    }
    bool operator==( const Point &rhs ) const {
        return x == rhs.x && y == rhs.y;
    }
};

namespace std {
    template<> struct hash<Point> {
        size_t operator()( const Point &p ) const {
            return p.x * MAXN + p.y;
        }
    };
}

void coloring( const Point &sp, int &u, int &d, int &l, int &r ) {
    if ( !sp.valid() || pic[sp.x][sp.y] != DOT ) { return; }
    pic[sp.x][sp.y] = CLR;
    u = min(u, sp.x); d = max(d, sp.x);
    l = min(l, sp.y); r = max(r, sp.y);
    for( int i = 0; i < sizeof(dx)/sizeof(dx[0]); ++i ) {
        coloring( Point(sp.x+dx[i],sp.y+dy[i]), u, d, l, r );
    }
}

void reachingout( Point sp, Point &ep ) {
    unordered_set<Point> s;
    s.insert(sp);
    queue<Point> q;
    q.push( sp );
    while( !q.empty() ) {
        Point p = q.front(); q.pop();
        for( int i = 0; i < sizeof(dx)/sizeof(dx[0]); ++i ) {
            Point np(p.x+dx[i], p.y+dy[i]);
            if( np.valid() && pic[np.x][np.y] == CLR && !s.count(np) ) {
                s.insert( np );
                q.push( np );
            }
        }
        ep = p;
    }
}

int main()
{
    while( 2 == scanf("%d %d", &H, &W) ) {
        for( int i = 0; i < H; ++i ) {
            scanf( "%s", pic[i] );
        }
        int countM = 0;
        int countS = 0;
        for( int x = 0; x < H; ++x ) {
            for( int y = 0; y < W; ++y ) {
                if( pic[x][y] != DOT ) { continue; }
                int u = H, d = 0, l = W, r = 0;
                Point sp( x, y ), ep1, ep2;
                coloring( sp, u, d, l, r );
                reachingout( sp,  ep1 );
                reachingout( ep1, ep2 );
                pic[ep1.x][ep1.y] = BEG;
                pic[ep2.x][ep2.y] = END;
                Point mid( (ep1.x+ep2.x)/2, (ep1.y+ep2.y)/2 );
                Point center(      (u+d)/2,         (l+r)/2 );
                Point &m = mid, &c = center;
                pic[m.x][m.y] = MID;
                if( abs(m.x-c.x)+abs(m.y-c.y) < ((r-l)+(d-u)) / 5 ) { // '4' not work.
                    ++countS;
                } else {
                    ++countM;
                }
            }
        }
        for( int i = 0; i < H; ++i ) {
            // fprintf( stderr, "%s\n", pic[i] );
        }
        printf("%d %d\n", countM, countS);
    }
}