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;
}