AOJ 0569 Illumination
JOI予選のとき、問題文を読む前からあきらめてしまった問題。
今回やってみたら20分でできた。成長したなー。
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569
解法
六角形の移動先配列を持ちながら深さ優先探索
#include <cstdio> #include <algorithm> using namespace std; const int dx[2][6] = {{-1, 0, 1, 1, 1, 0}, {-1, -1, 0, 1, 0, -1}}; const int dy[] = { 0, -1, -1, 0, 1, 1}; const int MAX_HW = 100; int H, W; int a[MAX_HW+3][MAX_HW+3]; int ans; void dfs(int x, int y){ a[x][y] = 2; for(int i=0; i<6; ++i){ int nx = x + dx[(y+1) % 2][i]; int ny = y + dy[i]; if(0<=nx&&nx<=W+1&&0<=ny&&ny<=H+1){ if(a[nx][ny] == 1) ++ans; else if(a[nx][ny] == 0) dfs(nx, ny); } } } int main(){ ans = 0; scanf("%d %d", &W, &H); for(int i=1; i<=H; ++i) for(int j=1; j<=W; ++j) scanf("%d", &a[j][i]); dfs(0, 0); printf("%d\n", ans); return 0; }