Codeforces Round #168 (Div. 2) B. Convex Shape

訳

n*mのグリッドが与えられ、1マスごとに黒色か白色の情報が与えられる。以下の条件を満たすとき凸の図形である。

• 黒色のマスから隣接する黒色のマスに移動することができ、移動する向きを2回以上変えずに全ての黒色のマスに辿り着くことができる。

与えられたグリッドが凸の図形であればYES、違うのであればNOを出力する。

int n, m;
char panel[64][64];
int check[64][64];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
// 0:down 1:right 2:up 3:left

bool isPanel(int y, int x) {
    return 0 <= x && 0 <= y && x < m && y < n;
}

void dfs(int y, int x, int dir, bool c) {
    if(dir == -1) {
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if(isPanel(ny, nx) && panel[ny][nx] == 'B') {
                check[ny][nx] = check[y][x] + 1;
                dfs(ny, nx, i, c);
            }
        }
    } else {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(isPanel(ny, nx) && panel[ny][nx] == 'B' && (check[ny][nx] == 0 || check[y][x] < check[ny][nx])) {
            check[ny][nx] = check[y][x] + 1;
            dfs(ny, nx, dir, c);
        }

        if(c) {

            int othdir = (dir + 1) % 4;
            nx = x + dx[othdir], ny = y + dy[othdir];
            if(isPanel(ny, nx) && panel[ny][nx] == 'B' && (check[ny][nx] == 0 || check[y][x] < check[ny][nx])) {
                check[ny][nx] = check[y][x] + 1;
                dfs(ny, nx, othdir, false);
            }

            othdir = (dir + 3) % 4;
            nx = x + dx[othdir], ny = y + dy[othdir];
            if(isPanel(ny, nx) && panel[ny][nx] == 'B' && (check[ny][nx] == 0 || check[y][x] < check[ny][nx])) {
                check[ny][nx] = check[y][x] + 1;
                dfs(ny, nx, othdir, false);
            }
        }
    }

    return;
}

int main()
{
    cin >> n >> m;
    int sx = 0, sy = 0;
    for(int i = 0; i < n; i++) {
        cin >> panel[i];
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(panel[i][j] == 'B') {
                memset(check, 0, sizeof check);
                check[i][j] = 1;
                dfs(i, j, -1, 1);

                for(int k = 0; k < n; k++) {
                    for(int l = 0; l < m; l++) {
                        if(panel[k][l] == 'B' && !check[k][l]) {
                            puts("NO");
                            return 0;
                        }
                    }
                }
            }
        }
    }

    puts("YES");
}

冷えた。最近ひどいなぁ…