【图论】格子图

其实格子图很可能会和棋盘格染色有关。

namespace BFS {

    const int MAXN = 1e3 + 10;
    const int MAXM = 1e3 + 10;
    const int di[] = {0, 0, -1, 1, -1, -1, 1, 1};
    const int dj[] = {-1, 1, 0, 0, -1, 1, -1, 1};

    int n, m;
    char g[MAXN][MAXM];

    bool vis[MAXN][MAXM];
    queue<pii> Q;

    bool valid(int i, int j) {
        if(1 <= i && i <= n && 1 <= j && j <= m) {
            if(!vis[i][j])
                return 1;
        }
        return 0;
    }

    void bfs(int si, int sj) {
        for(int i = 1; i <= n; ++i)
            fill(vis[i] + 1, vis[i] + 1 + m, 0);
        while(!Q.empty())
            Q.pop();
        vis[si][sj] = 1;
        Q.push({si, sj});
        while(!Q.empty()) {
            int ui = Q.front().first;
            int uj = Q.front().second;
            Q.pop();
            for(int k = 0; k < 4; ++k) {
                int vi = ui + di[k];
                int vj = uj + dj[k];
                if(valid(vi, vj)) {
                    vis[vi][vj] = 1;
                    Q.push({vi, vj});
                }
            }
        }
    }

}