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"); }
冷えた。最近ひどいなぁ…