読者です 読者をやめる 読者になる 読者になる

AOJ0569 Illumination

AOJ0569
AIZU ONLINE JUDGE

適当にdfsするとできた
前の予選の時は全然出来なかったなあ。

#include <cstdio>
using namespace std;

int w, h, ans;
int bu[110][110];
bool used[110][110];
int dx[2][6] = {{-1,-1,0,1,0,-1}, {-1, 0, 1, 1, 1, 0}};
int dy[6] = {0,-1,-1,0,1,1};

bool in(int nx, int ny){ return 0 <= nx && nx <= w + 1 && 0 <= ny && ny <= h + 1 && !used[nx][ny]; }

void solve(int x, int y){
    used[x][y] = true;
    for(int i = 0; i < 6; i++){
	int nx = x + dx[y & 1][i];
	int ny = y + dy[i];
	if(in(nx,ny)){
	    if(bu[nx][ny] == 1) ans++;
	    else solve(nx, ny);
	}
    }
}

int main(){
    scanf("%d %d", &w, &h);
    for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) scanf("%d", &bu[j][i]);
    solve(0,0);
    printf("%d\n", ans);
    return 0;
}