2010年11月14日日曜日

TopCoder 練習 Islands(SRM 477 Div1 Easy)

Islands(SRM 477 Div1 Easy)

■問題
六角セルのフィールドが与えられる.各セルはWaterかLandである.WaterセルとLandセルに挟まれたBeachの合計長は幾らか.

■解法
あるセルに隣接するセルは6つあるので,各セルの右,右下,左下を調べれば良い.

public class Islands{
public int beachLength(String[] str){
int ret=0;
// j:even (i+1,j), (i,j+1), (i-1,j+1)
// j:odd (i+1,j), (i+1,j+1), (i,j+1)
int n=str.length;
int m=str[0].length();
for(int j=0;j<n;j++){
for(int i=0;i<m;i++){
int[] dx, dy;
if(j%2==0){
dx=new int[]{1,0,-1};
dy=new int[]{0,1,1};
}else{
dx=new int[]{1,1,0};
dy=new int[]{0,1,1};
}
for(int d=0;d<3;d++){
int x=i+dx[d];
int y=j+dy[d];
if(0<=x&x<m&&0<=y&&y<n&&str[j].charAt(i)!=str[y].charAt(x)){
ret++;
}
}
}
}
return ret;
}
}

0 件のコメント: