[hdu5254]BFS

题意：如果一个格子的相邻四个格子中存在两个格子被标记，且这两个格子有公共点，那么这个格子也被标记。给定初始的标记状态，求最终有多少个格子被标记了

思路：依次对每个格子进行处理，看它能否”生成“新的被标记点。考虑当前点的四个相邻点，如果能被当前点生成，将它加入标记表，并入队，这样直到队列为空是的标记表就是终态。标记是永久标记，因为如果当前格子的四个相邻点不能在当前时刻由当前点生成，那么即便在以后的时刻可以由当前点生成，也完全可以由其它节点来生成它们，效果是等价的，因此标记是永久的。

#pragma comment(linker, "/STACK:10240000,10240000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
bool map[567][567];
queue<pair<int, int> > Q;
int n, m;
 
bool inMap(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
bool chk(int x, int y) {
    return inMap(x, y) && map[x][y];
}
bool chk(int x, int y, int i) {
    return chk(x + (dx[i] == 0), y + (dy[i] == 0)) ||
        chk(x - (dx[i] == 0), y - (dy[i] == 0));
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int T, cas = 0, k;
    cin >> T;
    while (T --) {
        cin >> n >> m;
        cin >> k;
        int ans = k;
        memset(map, 0, sizeof(map));
        while (!Q.empty()) Q.pop();
        for (int i = 0; i < k; i ++) {
            int u, v;
            scanf("%d%d", &u, &v);
            u --; v --;
            if (map[u][v]) ans --;
            map[u][v] = true;
            Q.push(make_pair(u, v));
        }
        while (!Q.empty()) {
            pair<int, int> H = Q.front(); Q.pop();
            for (int i = 0; i < 4; i ++) {
                int x = H.first + dx[i], y = H.second + dy[i];
                if (inMap(x, y) && !map[x][y]) {
                    if (chk(x, y, i)) {
                        map[x][y] = true;
                        Q.push(make_pair(x, y));
                        ans ++;
                    }
                }
            }
        }
        printf("Case #%d:
%d
", ++ cas, ans);
    }
    return 0;
}