問題
H＊Wの大きさである２次元の座標があり、そこにできるだけ多くの
石を置きたい。
ただし、それぞれの石の距離についてユークリッド距離が２にならないようにしたい。
このとき、最も多くおける石の個数を求める。
解き方
ユークリッド距離が２になりうるセルについて、４つの区間に分けることができる。
この区間はそれぞれどのような石の置かれ方をされてもユークリッド距離が
２になることはない。
あとは、各区間について置ける最大の石の個数を求めればよい。
区間中のセルの数をDFSで求め、その（セルの数＋１）／２が
置くことができる最大の石の個数となる。
コード
int used[1010][1010];
int dr[]={2,0,-2,0},dc[]={0,2,0,-2};
int w,h,cnt;
class NotTwo {
public:
void dfs(int r,int c){
used[r][c]=1;
cnt++;
FORE(i,0,4){
int nr=r+dr[i],nc=c+dc[i];
if(0<=nr && nr<h && 0<=nc && nc<w && !used[nr][nc]){
dfs(nr,nc);
}
}
}
int maxStones(int width, int height) {
int ret=0;
w=width,h=height;
memset(used,0,sizeof(used));
FORE(i,0,height)FORE(j,0,width)if(used[i][j]==0){
cnt=0;
dfs(i,j);
ret+=(cnt+1)/2;
}
return ret;
}
};
int dr[]={2,0,-2,0},dc[]={0,2,0,-2};
int w,h,cnt;
class NotTwo {
public:
void dfs(int r,int c){
used[r][c]=1;
cnt++;
FORE(i,0,4){
int nr=r+dr[i],nc=c+dc[i];
if(0<=nr && nr<h && 0<=nc && nc<w && !used[nr][nc]){
dfs(nr,nc);
}
}
}
int maxStones(int width, int height) {
int ret=0;
w=width,h=height;
memset(used,0,sizeof(used));
FORE(i,0,height)FORE(j,0,width)if(used[i][j]==0){
cnt=0;
dfs(i,j);
ret+=(cnt+1)/2;
}
return ret;
}
};