洛谷 P1454 圣诞夜的极光

最近做了，然后问了问学长做了没有，lfd是圣诞夜做的....
有点后悔，我做早了.
我也想要圣诞夜有人陪我看极光......
传送门

思路：

因为是曼哈顿距离小于2,就算在一个图中，
那么中间的点为起点的话，
那么一共有12与他相邻的点和他属于一个图案...
like this：

那么我们就可以按照这12个点与中间的(0,0)点的距离来进行BFS

代码：

//19-08-30
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define N 100010
#define M 110

using namespace std;
struct node {
    int x, y;
};
int f[M][M], n, m, ans; char s[M][M];
int next[12][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1},{-2,0},{0,-2},{0,2},{2,0}};

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

void bfs(int p, int q) {
    queue<node> qa;
    f[p][q] = 1;
    qa.push((node){p, q});
    while (!qa.empty()) {
        node a = qa.front(); qa.pop();
        for (int i = 0; i < 12; i++) {
            int x = a.x + next[i][0], y = a.y + next[i][1];
            if (x < 1 && x > n && y < 1 && y > n) continue;
            if (f[x][y] == 0 && s[x][y] == '#') {
                f[x][y] = 1;
//              ans++;
                qa.push((node) {x, y});
            }
        }
    } 
}

int main() {
    n = read(), m = read();
    char ch;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) 
            cin >> s[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (s[i][j] == '#' && f[i][j] == 0) 
                bfs(i, j), ans++;
    cout << ans;
}