class Ideone {
public static void main
(String[] args
){ System.
out.
println("2x2:\t" + solve
(1)); System.
out.
println("4x4:\t" + solve
(2)); System.
out.
println("6xt:\t" + solve
(3)); System.
out.
println("8x8:\t" + solve
(4)); System.
out.
println("10x10:\t" + solve
(5)); }
static int solve(int n){
int m =2*n;
int[][] b = new int[m][m];
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
b[i][j]=0;
}
}
return count(m,m*m,m*m/2,m*m/2,0,b);
}
static int count(int n,int sqLeft, int bLeft, int wLeft, int count, int[][] b){
if(sqLeft == 0){
/*for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
System.out.print(b[i][j]);
}
System.out.println();
}
System.out.println();*/
return count+1;
}
int x=(sqLeft-1)%n;
int y=(sqLeft-1)/n;
if(wLeft==0){
if(y!=0){
if ((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!= 1)) {
b[x][y] = 2;
return count(n, sqLeft-1, bLeft-1, wLeft, count, b);
} else {
return 0;
}
} else {
b[x][y]=2;
return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
}
} else if(bLeft==0){
if(y!=n-1){
if((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
b[x][y]=1;
return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
} else {
return 0;
}
} else {
b[x][y]=1;
return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
}
} else{
if(y==0){
if((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
int[][] c=new int[n][n];
for(int i = 0; i < n; i++){
System.
arraycopy(b
[i
],
0, c
[i
],
0, n
); }
b[x][y]=2;
c[x][y]=1;
return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
} else {
b[x][y]=2;
return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
}
}else if(y==n-1){
if((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1)){
int[][] c=new int[n][n];
for(int i = 0; i < n; i++){
System.
arraycopy(b
[i
],
0, c
[i
],
0, n
); }
b[x][y]=2;
c[x][y]=1;
return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
} else {
b[x][y]=1;
return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
}
}else{
if(((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1))&&((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2))){
int[][] c=new int[n][n];
for(int i = 0; i < n; i++){
System.
arraycopy(b
[i
],
0, c
[i
],
0, n
); }
b[x][y]=2;
c[x][y]=1;
return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
} else if ((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1)){
b[x][y]=2;
return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
} else if ((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
b[x][y]=1;
return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
} else {
return 0;
}
}
}
}
}
Y2xhc3MgSWRlb25lIHsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpewoJCVN5c3RlbS5vdXQucHJpbnRsbigiMngyOlx0IiArIHNvbHZlKDEpKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIjR4NDpcdCIgKyBzb2x2ZSgyKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCI2eHQ6XHQiICsgc29sdmUoMykpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiOHg4Olx0IiArIHNvbHZlKDQpKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIjEweDEwOlx0IiArIHNvbHZlKDUpKTsKCX0KCXN0YXRpYyBpbnQgc29sdmUoaW50IG4pewoJCWludCBtID0yKm47CgkJaW50W11bXSBiID0gbmV3IGludFttXVttXTsKCQlmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKCQkJZm9yKGludCBqID0gMDsgaiA8IG07IGorKyl7CgkJCQliW2ldW2pdPTA7CgkJCX0KCQl9CgkJcmV0dXJuIGNvdW50KG0sbSptLG0qbS8yLG0qbS8yLDAsYik7Cgl9CglzdGF0aWMgaW50IGNvdW50KGludCBuLGludCBzcUxlZnQsIGludCBiTGVmdCwgaW50IHdMZWZ0LCBpbnQgY291bnQsIGludFtdW10gYil7CgkJaWYoc3FMZWZ0ID09IDApewoJCQkvKmZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspewoJCQkJZm9yKGludCBqID0gMDsgaiA8IG47IGorKyl7CgkJCQkJU3lzdGVtLm91dC5wcmludChiW2ldW2pdKTsKCQkJCX0KCQkJCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJCQl9CgkJCVN5c3RlbS5vdXQucHJpbnRsbigpOyovCgkJCXJldHVybiBjb3VudCsxOwoJCX0KCQlpbnQgeD0oc3FMZWZ0LTEpJW47CgkJaW50IHk9KHNxTGVmdC0xKS9uOwoJCWlmKHdMZWZ0PT0wKXsKCQkJaWYoeSE9MCl7CgkJCQlpZiAoKHg9PTA/dHJ1ZTpiW3gtMV1beS0xXSE9MSkmJih4PT1uLTE/dHJ1ZTpiW3grMV1beS0xXSE9IDEpKSB7CgkJCQkJYlt4XVt5XSA9IDI7CgkJCQkJcmV0dXJuIGNvdW50KG4sIHNxTGVmdC0xLCBiTGVmdC0xLCB3TGVmdCwgY291bnQsIGIpOwoJCQkJfSBlbHNlIHsKCQkJCQlyZXR1cm4gMDsKCQkJCX0KCQkJfSBlbHNlIHsKCQkJCWJbeF1beV09MjsKCQkJCXJldHVybiBjb3VudChuLHNxTGVmdC0xLGJMZWZ0LTEsd0xlZnQsY291bnQsYik7CgkJCX0KCQl9IGVsc2UgaWYoYkxlZnQ9PTApewoJCQlpZih5IT1uLTEpewoJCQkJaWYoKHg9PTA/dHJ1ZTpiW3gtMV1beSsxXSE9MikmJih4PT1uLTE/dHJ1ZTpiW3grMV1beSsxXSE9MikpewoJCQkJCWJbeF1beV09MTsKCQkJCQlyZXR1cm4gY291bnQobixzcUxlZnQtMSxiTGVmdCx3TGVmdC0xLGNvdW50LGIpOwoJCQkJfSBlbHNlIHsKCQkJCQlyZXR1cm4gMDsKCQkJCX0KCQkJfSBlbHNlIHsKCQkJCWJbeF1beV09MTsKCQkJCXJldHVybiBjb3VudChuLHNxTGVmdC0xLGJMZWZ0LHdMZWZ0LTEsY291bnQsYik7CgkJCX0KCQl9IGVsc2V7CgkJCWlmKHk9PTApewoJCQkJaWYoKHg9PTA/dHJ1ZTpiW3gtMV1beSsxXSE9MikmJih4PT1uLTE/dHJ1ZTpiW3grMV1beSsxXSE9MikpewoJCQkJCWludFtdW10gYz1uZXcgaW50W25dW25dOwoJCQkJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspewoJCQkJCQlTeXN0ZW0uYXJyYXljb3B5KGJbaV0sIDAsIGNbaV0sIDAsIG4pOwoJCQkJCX0KCQkJCQliW3hdW3ldPTI7CgkJCQkJY1t4XVt5XT0xOwoJCQkJCXJldHVybiBjb3VudChuLHNxTGVmdC0xLGJMZWZ0LHdMZWZ0LTEsY291bnQsYykrY291bnQobixzcUxlZnQtMSxiTGVmdC0xLHdMZWZ0LGNvdW50LGIpOwoJCQkJfSBlbHNlIHsKCQkJCQliW3hdW3ldPTI7CgkJCQkJcmV0dXJuIGNvdW50KG4sc3FMZWZ0LTEsYkxlZnQtMSx3TGVmdCxjb3VudCxiKTsKCQkJCX0KCQkJfWVsc2UgaWYoeT09bi0xKXsKCQkJCWlmKCh4PT0wP3RydWU6Ylt4LTFdW3ktMV0hPTEpJiYoeD09bi0xP3RydWU6Ylt4KzFdW3ktMV0hPTEpKXsKCQkJCQlpbnRbXVtdIGM9bmV3IGludFtuXVtuXTsKCQkJCQlmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKCQkJCQkJU3lzdGVtLmFycmF5Y29weShiW2ldLCAwLCBjW2ldLCAwLCBuKTsKCQkJCQl9CgkJCQkJYlt4XVt5XT0yOwoJCQkJCWNbeF1beV09MTsKCQkJCQlyZXR1cm4gY291bnQobixzcUxlZnQtMSxiTGVmdCx3TGVmdC0xLGNvdW50LGMpK2NvdW50KG4sc3FMZWZ0LTEsYkxlZnQtMSx3TGVmdCxjb3VudCxiKTsKCQkJCX0gZWxzZSB7CgkJCQkJYlt4XVt5XT0xOwoJCQkJCXJldHVybiBjb3VudChuLHNxTGVmdC0xLGJMZWZ0LHdMZWZ0LTEsY291bnQsYik7CgkJCQl9CgkJCX1lbHNlewoJCQkJaWYoKCh4PT0wP3RydWU6Ylt4LTFdW3ktMV0hPTEpJiYoeD09bi0xP3RydWU6Ylt4KzFdW3ktMV0hPTEpKSYmKCh4PT0wP3RydWU6Ylt4LTFdW3krMV0hPTIpJiYoeD09bi0xP3RydWU6Ylt4KzFdW3krMV0hPTIpKSl7CgkJCQkJaW50W11bXSBjPW5ldyBpbnRbbl1bbl07CgkJCQkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJCQkJCVN5c3RlbS5hcnJheWNvcHkoYltpXSwgMCwgY1tpXSwgMCwgbik7CgkJCQkJfQoJCQkJCWJbeF1beV09MjsKCQkJCQljW3hdW3ldPTE7CgkJCQkJcmV0dXJuIGNvdW50KG4sc3FMZWZ0LTEsYkxlZnQsd0xlZnQtMSxjb3VudCxjKStjb3VudChuLHNxTGVmdC0xLGJMZWZ0LTEsd0xlZnQsY291bnQsYik7CgkJCQl9IGVsc2UgaWYgKCh4PT0wP3RydWU6Ylt4LTFdW3ktMV0hPTEpJiYoeD09bi0xP3RydWU6Ylt4KzFdW3ktMV0hPTEpKXsKCQkJCQliW3hdW3ldPTI7CgkJCQkJcmV0dXJuIGNvdW50KG4sc3FMZWZ0LTEsYkxlZnQtMSx3TGVmdCxjb3VudCxiKTsKCQkJCX0gZWxzZSBpZiAoKHg9PTA/dHJ1ZTpiW3gtMV1beSsxXSE9MikmJih4PT1uLTE/dHJ1ZTpiW3grMV1beSsxXSE9MikpewoJCQkJCWJbeF1beV09MTsKCQkJCQlyZXR1cm4gY291bnQobixzcUxlZnQtMSxiTGVmdCx3TGVmdC0xLGNvdW50LGIpOwoJCQkJfSBlbHNlIHsKCQkJCQlyZXR1cm4gMDsKCQkJCX0KCQkJfQoJCX0KCX0KfQo=