Skip to content

Instantly share code, notes, and snippets.

@r2dev
Created January 29, 2016 02:06
Show Gist options
  • Save r2dev/3f684070a9234848bba3 to your computer and use it in GitHub Desktop.
Save r2dev/3f684070a9234848bba3 to your computer and use it in GitHub Desktop.
lol i dont understand 100% but almost 80%, but whatever
public class App {
private static int fieldWidth, fieldSize;
private static long[] result;
private static int[] fieldCheck, fieldCheckR;
private static int[] rotationOffset = new int[8],
rotationX = new int[8],
rotationY = new int[8];
private static int linkData[] = new int[4];
public static void main(String[] args) {
int cell = 8;
if (cell < 1) {
return;
} if (cell == 1) {
count(2);
} else {
count(cell);
}
for (int i = 0; i != cell + 1; i++) {
System.out.println(result[i]);
}
}
private static void count(int cell) {
fieldWidth = cell * 2 - 2;
fieldSize = (cell - 1) * (cell -1) * 2 + 1;
result = new long[cell + 1];
int[] pnField = new int[fieldSize];
int[] pnPutList = new int[fieldSize];
fieldCheck = new int[cell * cell];
fieldCheckR = new int[cell * cell];
linkData[0] = 1;
linkData[1] = fieldWidth;
linkData[2] = -1;
linkData[3] = - fieldWidth;
initOffset(cell);
countSub(cell, 0, pnField, pnPutList, 0 , 1);
}
private static void countSub(int n, int lv, int[] field, int[] putList,
int putno, int putlast) {
check(field, n, lv);
if (n == lv) {
return;
}
for (int i = putno; i != putlast; i++) {
int pos = putList[i];
field[pos] |= 1;
int k = 0;
for (int j = 0; j != 4; j++) {
int pos2 = pos + linkData[j];
if (0 <= pos2 && pos2 < fieldSize && field[pos2] == 0) {
field[pos2] = 2;
putList[putlast + k] = pos2;
k++;
}
}
countSub(n, lv + 1, field, putList, i + 1, putlast + k);
for (int j = 0; j != k; j++) {
field[putList[putlast + j]] = 0;
}
field[pos] = 2;
}
for (int i = putno; i != putlast; i++) {
int pos = putList[i];
field[pos] &= -2;
}
}
private static void initOffset(int n) {
rotationOffset[0] = 0;
rotationX[0] = 1;
rotationY[0] = n;
// 90
rotationOffset[1] = n - 1;
rotationX[1] = n;
rotationY[1] = -1;
// 180
rotationOffset[2] = n * n - 1;
rotationX[2] = -1;
rotationY[2] = -n;
// 270
rotationOffset[3] = n * n - n;
rotationX[3] = -n;
rotationY[3] = 1;
rotationOffset[4] = n - 1;
rotationX[4] = -1;
rotationY[4] = n;
// 90
rotationOffset[5] = 0;
rotationX[5] = n;
rotationY[5] = 1;
// 180
rotationOffset[6] = n * n - n;
rotationX[6] = 1;
rotationY[6] = -n;
// 270
rotationOffset[7] = n * n - 1;
rotationX[7] = -n;
rotationY[7] = -1;
}
private static void check(int[] field, int n, int lv) {
for (int i = 0; i != n * n; i++) {
fieldCheck[i] = 0;
}
int x, y;
outloop:
for (x = n; x < n * 2 - 2; x++) {
for (y = 0; y + x < fieldSize; y += fieldWidth) {
if ((field[x + y] & 1) != 0) {
break outloop;
}
}
}
int x2 = n - x;
for (int i = 0; i != fieldSize; i++) {
x = (i + n - 2) % fieldWidth;
y = (i + n - 2) / fieldWidth * n;
if ((field[i] & 1) != 0) {
fieldCheck[x + x2 + y] = 1;
}
}
int of1;
for (of1 = 0; of1 < fieldCheck.length && fieldCheck[of1] == 0; of1++){}
boolean c = true;
int r;
for (r = 1; r < 4 && c; r++) {
for (x = 0; x < n; x++) {
for (y = 0; y < n; y++) {
int pos = rotationOffset[r] + rotationX[r] * x + rotationY[r] * y;
fieldCheckR[pos] = fieldCheck[x + y * n];
}
}
int of2;
for (of2 = 0; of2 < fieldCheckR.length && fieldCheckR[of2] == 0; of2++) {}
of2 -= of1;
int ed = (of2 > 0) ? (n * n - of2) : (n * n);
for (int i = of1; i != ed; i++) {
if (fieldCheck[i] > fieldCheckR[i + of2])
break;
if (fieldCheck[i] < fieldCheckR[i + of2]) {
c = false;
break;
}
}
}
if (c) {
result[lv]++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment