Last active
November 8, 2021 15:00
-
-
Save skeeto/ade312b93d0a0021e1bc8de9178bd4e3 to your computer and use it in GitHub Desktop.
Mazelog Monthly Challenge Solvers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
static char game[8][8] = { | |
"nbrnnnnr", | |
"rbnn n n", | |
"bnnnrbb ", | |
"rnrkknnb", | |
"rbrkk n ", | |
"bnn r n", | |
"nnnnn bn", | |
"n nnnnn", | |
}; | |
static const char knight[] = { | |
1, -2, 2, -1, 2, 1, 1, 2, -1, 2, -2, 1, -2, -1, -1, 2 | |
}; | |
static const char bishop[] = { | |
1, -1, 1, 1, -1, 1, -1, -1 | |
}; | |
static const char rook[] = { | |
0, -1, 1, 0, 0, 1, -1, 0 | |
}; | |
static const char king[] = { | |
0, -1, 1, -1, 1, 0, 1, 1, 0, 1, -1, 1, -1, 0, -1, -1 | |
}; | |
static struct { | |
char x; | |
char y; | |
} path[32]; | |
unsigned best = sizeof(path) / sizeof(path[0]); | |
static void | |
output(unsigned n) | |
{ | |
if (n < best) { | |
best = n; | |
for (unsigned i = 0; i < n; i++) | |
printf("%d%c", 8 * path[i].y + path[i].x + 1, " \n"[i == n - 1]); | |
} | |
} | |
#define VALID(x, y) ((x) >= 0 && (x) < 8 && (y) >= 0 && (y) < 8) | |
static void | |
solve(unsigned n) | |
{ | |
if (n == best) | |
return; | |
int x = path[n - 1].x; | |
int y = path[n - 1].y; | |
if (x == 7 && y == 7) { | |
output(n); | |
return; | |
} | |
char c = game[y][x]; | |
game[y][x] = '#'; | |
switch (c) { | |
case 'k': | |
case 'n': { | |
const char *base = c == 'n' ? knight : king; | |
for (int i = 0; i < 8; i++) { | |
int tx = x + base[i * 2 + 0]; | |
int ty = y + base[i * 2 + 1]; | |
if (VALID(tx, ty)) { | |
path[n].x = (char)tx; | |
path[n].y = (char)ty; | |
solve(n + 1); | |
} | |
} | |
} break; | |
case 'b': | |
case 'r': { | |
const char *base = c == 'r' ? rook : bishop; | |
for (int i = 0; i < 4; i++) { | |
int tx = x; | |
int ty = y; | |
do { | |
tx += base[i * 2 + 0]; | |
ty += base[i * 2 + 1]; | |
} while (VALID(tx, ty) && game[ty][tx] == ' '); | |
if (VALID(tx, ty)) { | |
path[n].x = (char)tx; | |
path[n].y = (char)ty; | |
solve(n + 1); | |
} | |
} | |
} break; | |
} | |
game[y][x] = c; | |
} | |
int | |
main(void) | |
{ | |
solve(1); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define N 4 | |
static const signed char grid[] = { | |
+3, -1, +1, -2, | |
-1, +1, -1, +2, | |
-1, +0, +0, -1, | |
-1, +2, +1, +0, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1 | |
}; | |
static int | |
solve(int *p, int n, int v, int bestn) | |
{ | |
if (p[n - 1] == N * N - 1) { | |
/* Found a solution. */ | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
for (int i = 0; i < (int)(sizeof(moves) / sizeof(*moves) / 2); i++) { | |
int x = p[n - 1] % N; | |
int y = p[n - 1] / N; | |
int tx = x + moves[i * 2 + 0] * v; | |
int ty = y + moves[i * 2 + 1] * v; | |
int t = ty * N + tx; | |
if (tx == 0 && ty == 0) { | |
/* Special rule: (0, 0) resets the value. */ | |
p[n] = 0; | |
bestn = solve(p, n + 1, grid[0], bestn); | |
} else if (tx >= 0 && tx < N && ty >= 0 && ty < N && | |
grid[t] + v > 0 && grid[t] + v < N) { | |
p[n] = t; | |
bestn = solve(p, n + 1, grid[t] + v, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[16] = {0}; | |
solve(path, 1, grid[0], sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define H 5 | |
#define W 6 | |
#define TARGET (W * H - 1) | |
static const signed char grid[] = { | |
+3, +0, +1, +1, -2, +1, | |
+1, -1, +1, +0, +1, +2, | |
+1, +1, -1, -1, +2, +1, | |
+1, -1, +0, +2, -2, +1, | |
+0, -1, +3, -3, +2, +0, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1 | |
}; | |
static int | |
solve(int *p, int n, int v, int bestn) | |
{ | |
if (p[n - 1] == TARGET) { | |
/* Found a solution. */ | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
for (int i = 0; i < (int)(sizeof(moves) / sizeof(*moves) / 2); i++) { | |
int x = p[n - 1] % W; | |
int y = p[n - 1] / W; | |
int tx = x + moves[i * 2 + 0] * v; | |
int ty = y + moves[i * 2 + 1] * v; | |
int t = ty * W + tx; | |
if (tx == 0 && ty == 0) { | |
/* Special rule: (0, 0) resets the value. */ | |
p[n] = 0; | |
bestn = solve(p, n + 1, grid[0], bestn); | |
} else if (tx >= 0 && tx < W && | |
ty >= 0 && ty < H && | |
grid[t] + v >= 0) { | |
p[n] = t; | |
bestn = solve(p, n + 1, grid[t] + v, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[24] = {0}; | |
solve(path, 1, grid[0], sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 5 | |
#define T 21 | |
static const struct { | |
enum { M, A } op; | |
int value; | |
} grid[] = { | |
{M, +0}, {A, +1}, {M, +3}, {A, +2}, {A, -2}, | |
{A, +1}, {M, +4}, {M, +2}, {A, -2}, {A, -2}, | |
{M, +2}, {A, +2}, {A, -2}, {A, +2}, {M, +2}, | |
{A, +2}, {A, -2}, {M, +2}, {M, +4}, {A, +1}, | |
{A, +0}, {A, +2}, {M, +3}, {A, +3}, {A, +1}, | |
}; | |
static const int moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1 | |
}; | |
static int | |
solve(int *p, int n, int v, int bestn) | |
{ | |
switch (grid[p[n]].op) { | |
case M: | |
v *= grid[p[n]].value; | |
break; | |
case A: | |
v += grid[p[n]].value; | |
break; | |
} | |
if (p[n] == H * W - 1 && v == T) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
for (int i = 0; i < 4; i++) { | |
int xx = x + moves[i * 2 + 0]; | |
int yy = y + moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, v, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[24] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 8 | |
#define H 8 | |
static const signed char grid[] = { | |
+3, +3, -3, +5, +6, +3, +6, +3, | |
+3, +6, +6, +3, +3, +5, +6, -3, | |
+3, -3, -3, +3, +3, +2, +3, +3, | |
+3, +3, +5, +3, +3, +3, -3, +3, | |
+2, +3, -3, +3, +3, +3, -3, +3, | |
-3, +6, +3, +3, +3, -2, +3, -2, | |
+3, -3, +3, +4, +3, +3, +3, +3, | |
+3, +3, -3, +6, +3, +3, -3, +0, | |
}; | |
static const signed char moves[][8] = { | |
{-1, +0, +1, +0, +0, -1, +0, +1}, | |
{-1, -1, +1, +1, +1, -1, -1, +1}, | |
}; | |
static int | |
solve(int *p, int n, int m, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int v = abs(grid[p[n]]); | |
int x = p[n] % W; | |
int y = p[n] / W; | |
if (grid[p[n]] < 0) | |
m = !m; | |
for (int i = 0; i < 4; i++) { | |
int xx = x + v * moves[m][i * 2 + 0]; | |
int yy = y + v * moves[m][i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, m, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[24] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 8 | |
#define H 8 | |
enum direction {UU, UR, RR, DR, DD, DL, LL, UL}; | |
static const signed char grid[] = { | |
DD, DR, RR, DR, DD, DR, LL, DL, | |
UR, DD, DR, DR, DR, RR, UR, DD, | |
RR, UR, UU, UR, LL, DL, RR, LL, | |
UR, UR, DL, UL, DR, LL, UU, UL, | |
UU, DR, DD, UR, LL, UL, DR, UL, | |
UR, RR, UL, DR, UR, UU, DL, DL, | |
DR, UL, RR, UR, UU, UL, UU, UL, | |
UR, LL, UR, UR, UL, UL, RR, -1, | |
}; | |
static const signed char moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, | |
+0, +1, -1, +1, -1, +0, -1, -1, | |
}; | |
#define VALID(x, y) ((x) >= 0 && (x) < W && (y) >= 0 && (y) < H) | |
#define VISIT(v, n) ((v) | (1ULL << (n))) | |
#define VISITED(v, n) ((v) & (1ULL << (n))) | |
static int | |
solve(int *p, int n, int m, int bestn, unsigned long long visit) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int sx = p[n] % W; | |
int sy = p[n] / W; | |
int dx = moves[grid[p[n]] * 2 + 0]; | |
int dy = moves[grid[p[n]] * 2 + 1]; | |
for (int x = sx + dx, y = sy + dy; VALID(x, y); x += dx, y += dy) { | |
int next = x + y * W; | |
if (!VISITED(visit, next)) { | |
p[n + 1] = next; | |
visit = VISIT(visit, next); | |
bestn = solve(p, n + 1, m, bestn, visit); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[24] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path), VISIT(0, 1)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define S 6 | |
enum shape {SC=0x00, ST=0x01, SX=0x02, SP=0x03, SH=0x04, SV=0x05, SS=0x06}; | |
enum color {CB=0x10, CO=0x20, CP=0x30, CG=0x40, CR=0x50, CY=0x60}; | |
static const unsigned char grid[] = { | |
SC|CB, ST|CO, SX|CP, SX|CG, SC|CR, ST|CG, | |
SV|CR, ST|CR, ST|CB, SX|CB, SC|CY, SX|CO, | |
SC|CO, SH|CG, SP|CP, SH|CO, SC|CP, SP|CR, | |
ST|CO, SH|CB, SV|CB, SS|CO, SS|CR, SH|CR, | |
ST|CR, SC|CG, SS|CG, SS|CR, SX|CP, SC|CO, | |
SV|CY, SP|CO, SV|CG, SP|CP, SX|CY, SC|CP, | |
}; | |
static const signed char moves[] = { | |
+0, -1, +1, +0, +0, +1, -1, +0, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == S * S - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int s = (n % 2) * 4; | |
int x = p[n] % S; | |
int y = p[n] / S; | |
unsigned v = (grid[p[n]] >> s) & 0xf; | |
for (int d = 0; d < 4; d++) { | |
for (int r = 1; r < S; r++) { | |
int cx = x + r * moves[d * 2 + 0]; | |
int cy = y + r * moves[d * 2 + 1]; | |
if (cx < 0 || cx >= S || cy < 0 || cy >= S) | |
break; | |
int cp = cy * S + cx; | |
unsigned cv = (grid[cp] >> s) & 0x0f; | |
if (v == cv) { | |
p[n + 1] = cp; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[24] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 5 | |
enum direction { UU, UR, RR, DR, DD, DL, LL, UL }; | |
static const char grid[] = { | |
RR, DL, DR, DL, LL, | |
UU, LL, DL, DL, LL, | |
DR, DR, UL, UL, UR, | |
UR, LL, UR, DR, DD, | |
DL, DD, DR, UL, 0 | |
}; | |
static const signed char moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int v = (grid[p[n]] + n % 4 / 2 * 4) % 8; | |
int x = p[n] % W; | |
int y = p[n] / W; | |
for (int d = 1; d < W; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[24] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 5 | |
#define H 5 | |
static const signed char grid[] = { | |
+3, -1, +1, -1, +1, | |
+1, +1, +0, -1, -2, | |
+1, +1, -1, +0, -2, | |
-1, +1, -1, +1, +3, | |
+0, -1, +2, +0, +0, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
}; | |
static int | |
solve(int *p, int n, int d, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int j = x == 0 && y == 0 ? grid[0] : d + grid[p[n]]; | |
if (j > 0) { | |
for (int i = 0; i < 4; i++) { | |
int xx = x + j * moves[i * 2 + 0]; | |
int yy = y + j * moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, j, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[16] = {0}; | |
solve(path, 0, grid[0], sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 6 | |
#define H 6 | |
static const char grid[] = { | |
2, 0, 3, 0, 0, 2, | |
4, 0, 0, 0, 2, 0, | |
0, 0, 0, 3, 0, 0, | |
1, 2, 3, 0, 0, 0, | |
0, 2, 4, 0, 3, 3, | |
0, 0, 0, 3, 0, 0, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
}; | |
static int | |
solve(int *p, int n, int j, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int d = grid[p[n]] ? grid[p[n]] : j; | |
for (int i = 0; i < 4; i++) { | |
int xx = x + d * moves[i * 2 + 0]; | |
int yy = y + d * moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, d, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[16] = {0}; | |
solve(path, 0, grid[0], sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 7 | |
#define H 7 | |
enum {UU, UR, RR, DR, DD, DL, LL, UL, TT}; | |
static const char grid[] = { | |
TT, DR, DL, DR, DD, DR, TT, | |
RR, RR, DL, UL, RR, UL, LL, | |
UR, UU, UU, UR, LL, LL, LL, | |
DR, DR, RR, UU, DR, UR, UL, | |
DR, UR, UU, RR, UU, UU, LL, | |
UU, UR, DR, RR, UU, DR, DL, | |
TT, UU, UR, UR, UU, UL, TT, | |
}; | |
static const signed char moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (grid[p[n]] == TT) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int d = grid[p[n]]; | |
for (int s = 1; ; s++) { | |
int xx = x + s * moves[d * 2 + 0]; | |
int yy = y + s * moves[d * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[12] = {24}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 5 | |
enum {P, R, B, K, X}; | |
static const char grid[] = { | |
R, B, P, R, B, | |
B, R, B, R, P, | |
P, P, P, B, B, | |
B, P, P, R, B, | |
B, P, K, B, X, | |
}; | |
static const signed char moves[] = { | |
0, 0, 8, 4, 16, 4, 24, 8, | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
-2, -1, -2, +1, +2, -1, +2, +1, | |
-1, -2, -1, +2, +1, -2, +1, +2, | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (grid[p[n]] == X) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int c = grid[p[n]] ? grid[p[n]] : last; | |
int off = moves[c * 2 + 0]; | |
int len = moves[c * 2 + 1]; | |
const signed char *m = moves + off; | |
for (int i = 0; i < len; i++) { | |
int xx = x + m[i * 2 + 0]; | |
int yy = y + m[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, c, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[18] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 4 | |
enum {UU, UR, RR, DR, DD, DL, LL, UL, TL, TR}; | |
static const char grid[] = { | |
DR, TL, DL, TR, TL, | |
TL, UU, DD, DD, LL, | |
TL, UR, DR, UL, UU, | |
TR, TL, TR, LL, 0, | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
int | |
main(void) | |
{ | |
long h = 0; | |
long t = 1; | |
static char queue[W * H * 16384L]; | |
static long fromq[W * H * 16384L]; | |
static char prevd[W * H * 16384L]; | |
queue[0] = 0; | |
fromq[0] = -1; | |
prevd[0] = grid[0]; | |
for (;;) { | |
int p = queue[h]; | |
int d = prevd[h]; | |
int x = p % W; | |
int y = p / W; | |
/* Solution found */ | |
if (p == W * H - 1) { | |
int n = 0; | |
int path[32]; | |
while (h >= 0) { | |
path[n++] = queue[h] + 1; | |
h = fromq[h]; | |
} | |
while (n--) | |
printf("%d%c", path[n], "\n "[!!n]); | |
break; | |
} | |
int v = grid[p]; | |
if (v == TL) { | |
v = (d + 6) % 8; | |
} else if (v == TR) { | |
v = (d + 2) % 8; | |
} | |
int dx = moves[v * 2 + 0]; | |
int dy = moves[v * 2 + 1]; | |
for (int i = 1; ; i++) { | |
int cx = x + i * dx; | |
int cy = y + i * dy; | |
if (cx < 0 || cx >= W || cy < 0 || cy >= H) | |
break; | |
queue[t] = cy * W + cx; | |
fromq[t] = h; | |
prevd[t] = v; | |
t++; | |
} | |
h++; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 6 | |
#define H 6 | |
enum {R = 0x10, G = 0x20, B = 0x30, V = 0x40, O = 0x50}; | |
enum {C = 0x01, D = 0x02, X = 0x03, P = 0x04, A = 0x05}; | |
static const char grid[] = { | |
B|A, G|C, G|P, G|X, G|A, G|A, | |
B|P, G|C, B|P, V|P, R|C, O|A, | |
O|A, O|D, V|X, B|C, O|P, B|A, | |
R|A, V|C, B|D, O|X, G|A, O|A, | |
O|X, O|C, B|X, G|P, R|X, G|C, | |
G|C, O|C, V|X, G|P, B|X, V|D, | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]]; | |
int s = v & 0x0f; | |
int c = v & 0xf0; | |
const int *m = moves + (n % 2) * 8; | |
for (int i = 0; i < 4; i++) { | |
for (int d = 1; ; d++) { | |
int xx = x + d * m[i * 2 + 0]; | |
int yy = y + d * m[i * 2 + 1]; | |
if (xx < 0 || xx >= W || yy < 0 || yy >= H) | |
break; | |
int t = grid[yy * W + xx]; | |
if ((t & 0x0f) == s || (t & 0xf0) == c) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[28] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 6 | |
#define H 6 | |
static const char grid[] = { | |
3, 2, 2, 2, 2, 3, | |
2, 3, 3, 1, 1, 1, | |
3, 1, 2, 2, 3, 2, | |
2, 3, 2, 2, 3, 1, | |
3, 3, 2, 1, 2, 3, | |
2, 1, 2, 1, 2, 1, | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int d = grid[p[n]]; | |
const int *m = moves + (n % 2) * 8; | |
for (int i = 0; i < 4; i++) { | |
int xx = x + d * m[i * 2 + 0]; | |
int yy = y + d * m[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[20] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 6 | |
#define H 6 | |
enum {P, R, B, K}; | |
enum {D, L = 0x10}; | |
static const char grid[] = { | |
D|B, D|K, L|B, D|R, D|K, L|R, | |
L|K, D|K, D|K, D|K, D|B, D|K, | |
D|K, D|K, L|K, L|B, D|K, D|K, | |
L|B, D|K, D|K, D|K, D|K, D|K, | |
L|B, L|R, L|K, L|B, D|K, L|B, | |
D|R, L|B, L|K, L|K, L|B, L|K, | |
}; | |
static const signed char moves[] = { | |
0, 0, 8, 4, 16, 4, 24, 8, | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
-2, -1, -2, +1, +2, -1, +2, +1, | |
-1, -2, -1, +2, +1, -2, +1, +2, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int g = ((n + 1) / 2) % 2; | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]] & ~L; | |
int off = moves[v * 2 + 0]; | |
int len = moves[v * 2 + 1]; | |
const signed char *m = moves + off; | |
for (int i = 0; i < len; i++) { | |
int xx = x + m[i * 2 + 0]; | |
int yy = y + m[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int t = yy * W + xx; | |
if (grid[t] >> 4== g) { | |
p[n + 1] = t; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[27] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {NN, SS, EE, WW, SE, NW, NE, SW}; | |
#define W 8 | |
#define H 8 | |
static const char grid[] = { | |
SS, EE, EE, SE, EE, SW, WW, WW, | |
NE, NE, SS, EE, SE, SE, NE, NW, | |
NE, NW, WW, SW, SW, SE, WW, NW, | |
NE, NE, NW, SE, EE, SS, NE, NN, | |
SE, WW, SS, EE, WW, EE, SS, SW, | |
NE, WW, NN, SE, SE, NE, SS, SS, | |
SE, NN, NN, NW, SS, NE, WW, NW, | |
NN, WW, NE, NE, NW, WW, NW, -1, | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]]; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[13] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {NN, SS, EE, WW, SE, NW, NE, SW}; | |
enum {B = 0x00, R = 0x10}; | |
#define W 5 | |
#define H 5 | |
static const char grid[] = { | |
B|SS, B|EE, B|EE, B|SS, R|SW, | |
B|NN, R|EE, R|SW, R|SS, B|SS, | |
B|SE, B|EE, R|SW, R|EE, R|WW, | |
B|EE, B|SW, B|NW, R|NW, B|SW, | |
B|NN, B|NN, B|WW, R|WW, 0, | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]] & 0x0f; | |
int t = ((n + 1) / 3) & 1; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int i = yy * W + xx; | |
int c = grid[i] >> 4; | |
if (c == t) { | |
p[n + 1] = i; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[26] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define C 0x80 | |
enum {A=0x01, E=0x02, X=0x03, D=0x04, P=0x05, S=0x06}; | |
enum {R=0x10, Y=0x20, B=0x30, V=0x40, O=0x50, G=0x60}; | |
#define W 6 | |
#define H 6 | |
static const unsigned char grid[] = { | |
0|R|A, 0|Y|E, 0|O|X, 0|O|E, 0|O|E, 0|G|E, | |
C|B|A, 0|B|D, 0|V|A, 0|B|P, 0|B|E, 0|R|E, | |
0|O|X, 0|R|E, 0|B|X, 0|R|X, 0|G|E, 0|O|P, | |
0|Y|P, 0|B|X, C|O|A, 0|Y|A, C|O|A, 0|O|E, | |
0|G|E, 0|R|E, 0|O|E, 0|V|A, 0|G|X, 0|V|A, | |
0|V|A, 0|B|A, 0|G|A, C|B|A, 0|R|E, 0|O|S, | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1, | |
}; | |
static int | |
solve(int *p, int n, int m, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int s = grid[p[n]] & 0x07; | |
int c = grid[p[n]] & 0x70; | |
for (int v = 0; v < 8; v++) { | |
for (int d = 1; ; d++) { | |
int tx = x + d * moves[v * 2 + 0]; | |
int ty = y + d * moves[v * 2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int i = ty * W + tx; | |
int ts = grid[i] & 0x07; | |
int tc = grid[i] & 0x70; | |
int to = grid[i] & 0x80; | |
if ((!m && s == ts) || (m && c == tc)) { | |
p[n + 1] = i; | |
bestn = solve(p, n + 1, to ? m : !m, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[30] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 5 | |
static const unsigned long grid = 0x848824; | |
static const int moves[] = {+0, -1, +0, +1, +1, +0, -1, +0}; | |
static int | |
solve(int *p, int n, int d, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (d > 0 && n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
for (int m = 0; m < 4; m++) { | |
int xx = x + d * moves[m * 2 + 0]; | |
int yy = y + d * moves[m * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int i = yy * W + xx; | |
int f = (grid >> i) & 1UL; | |
int dd; | |
p[n + 1] = i; | |
if (i == 0) | |
dd = 1; | |
else | |
dd = f ? d + 1: d - 1; | |
bestn = solve(p, n + 1, dd, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[20] = {0}; | |
solve(path, 0, 1, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {NN, NE, EE, SE, SS, SW, WW, NW}; | |
#define W 6 | |
#define H 6 | |
static const char grid[] = { | |
EE, SS, WW, SW, NW, WW, | |
SE, NE, NE, EE, WW, NE, | |
WW, NN, SS, NE, NN, WW, | |
SE, SW, NN, NN, NW, EE, | |
EE, SW, WW, SE, NW, EE, | |
NN, SS, NN, WW, NE, 0 | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int a = grid[p[n]]; | |
int r = n % 2 ? -1 : 1; | |
for (int d = 1; ; d++) { | |
int xx = x + r * d * moves[a * 2 + 0]; | |
int yy = y + r * d * moves[a * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[31] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {EE = 0, NL = 1, SS = 2, NR = 3}; | |
#define W 6 | |
#define H 6 | |
static const char grid[] = { | |
EE, NL, NR, SS, SS, NR, | |
NL, NL, NR, NR, SS, NR, | |
NL, NL, NL, NR, NR, NR, | |
SS, NL, NL, NL, NR, NR, | |
NL, SS, SS, NL, NL, NL, | |
NR, NL, SS, NL, NL, EE | |
}; | |
static const int moves[] = { | |
+0, -1, +1, +0, +0, +1, -1, +0, | |
}; | |
static int | |
solve(int *p, int n, int v, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int a = grid[yy * W + xx]; | |
if (a != SS) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, (v + a) % 4, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[25] = {0}; | |
solve(path, 0, 1, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {B=0x01, R=0x02, S=0x10, D=0x20, X=0x30, T=0x40, C=0x80}; | |
#define BEG 2 | |
#define END 22 | |
#define W 5 | |
#define H 5 | |
static const unsigned char grid[] = { | |
0|0|0, 0|0|0, 0|B|S, 0|0|0, 0|0|0, | |
0|0|0, 0|R|T, C|B|X, C|R|D, 0|0|0, | |
0|B|X, 0|B|T, 0|R|D, C|B|D, C|B|S, | |
0|0|0, C|B|S, 0|R|X, 0|R|S, 0|0|0, | |
0|0|0, 0|0|0, 0|0|D, 0|0|0, 0|0|0 | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int d, int bestn) | |
{ | |
if (p[n] == END) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int o = d % 2; | |
int a = grid[p[n]]; | |
int c = a & 0x07; | |
int s = a & 0x70; | |
if (a & C) | |
o = !o; | |
for (int i = 0; i < 4; i++) { | |
int j = i * 2 + o; | |
if (j != (d + 4) % 8) { // no u-turns | |
for (int v = 1; ; v++) { | |
int xx = x + v * moves[j * 2 + 0]; | |
int yy = y + v * moves[j * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int ti = yy * W + xx; | |
int ta = grid[ti]; | |
int tc = ta & 0x07; | |
int ts = ta & 0x70; | |
if (tc == c || ts == s) { | |
p[n + 1] = ti; | |
bestn = solve(p, n + 1, j, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[14] = {BEG}; | |
solve(path, 0, 3, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 6 | |
#define H 5 | |
static const signed char grid[] = { | |
+9, +1, -2, -2, -1, +1, | |
-1, +1, +1, +1, +1, +3, | |
-2, -1, +0, +1, +3, -1, | |
+1, -1, -3, +1, -1, -3, | |
-2, -3, +2, +1, +3, +0 | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
}; | |
static int | |
solve(int *p, int n, int d, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int j = d + grid[p[n]]; | |
if (j > 0) { | |
for (int i = 0; i < 4; i++) { | |
int xx = x + j * moves[i * 2 + 0]; | |
int yy = y + j * moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, j, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[34] = {0}; | |
solve(path, 0, -6, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 6 | |
#define H 6 | |
enum {P, R, B, K, X}; | |
static const char grid[] = { | |
R, P, P, B, B, R, | |
B, R, B, R, B, R, | |
R, B, P, P, B, B, | |
P, P, B, R, B, P, | |
B, B, P, B, K, P, | |
B, R, B, R, P, X, | |
}; | |
static const signed char moves[] = { | |
0, 0, 8, 4, 16, 4, 24, 8, | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
-2, -1, -2, +1, +2, -1, +2, +1, | |
-1, -2, -1, +2, +1, -2, +1, +2, | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (grid[p[n]] == X) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int c = grid[p[n]] ? grid[p[n]] : last; | |
int off = moves[c * 2 + 0]; | |
int len = moves[c * 2 + 1]; | |
const signed char *m = moves + off; | |
for (int i = 0; i < len; i++) { | |
int xx = x + m[i * 2 + 0]; | |
int yy = y + m[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
int loop = 0; | |
if (grid[p[n + 1]]) | |
for (int j = 0; !loop && j < n; j++) | |
if (p[j] == p[n + 1]) | |
loop = 1; | |
if (!loop) | |
bestn = solve(p, n + 1, c, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[26] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define C 0x80 | |
enum {NN, NE, EE, SE, SS, SW, WW, NW}; | |
enum {B = 0x10, R = 0x20, G = 0x40}; | |
#define W 6 | |
#define H 6 | |
static const unsigned char grid[] = { | |
0|G|EE, 0|G|NW, 0|R|EE, 0|B|SE, 0|B|NN, 0|G|SW, | |
0|G|EE, 0|R|NE, 0|R|SS, 0|B|NN, 0|R|EE, 0|R|EE, | |
0|G|WW, C|G|EE, 0|B|SW, 0|R|NE, 0|B|NE, 0|B|SW, | |
0|R|WW, 0|R|EE, 0|B|NE, 0|R|SE, 0|G|SE, C|G|EE, | |
0|G|SW, 0|B|SW, 0|G|SS, 0|G|NN, 0|G|SE, 0|R|EE, | |
0|B|NN, 0|G|SS, 0|G|NN, 0|R|EE, 0|R|SE, 0 | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int r, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]] & 0x0f; | |
int c = grid[p[n]] & 0x70; | |
if (r) | |
v = (v + 4) % 8; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int i = yy * W + xx; | |
int cc = grid[i] & 0x70; | |
if (cc != c) { | |
int rr = r; | |
if (grid[i] & 0x80) | |
rr = !rr; | |
p[n + 1] = i; | |
bestn = solve(p, n + 1, rr, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[32] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {A=0x01, E=0x02, X=0x03, C=0x04, P=0x05, S=0x06}; | |
enum {R=0x10, Y=0x20, B=0x30, V=0x40, O=0x50, G=0x60}; | |
#define W 6 | |
#define H 6 | |
static const unsigned char grid[] = { | |
R|C, B|E, O|S, O|X, V|C, G|E, | |
V|C, B|P, Y|X, G|X, Y|S, V|P, | |
O|A, V|A, V|S, G|E, V|C, B|E, | |
O|E, O|P, R|X, R|S, V|A, B|A, | |
Y|C, O|X, B|C, Y|S, B|A, G|A, | |
B|E, R|X, B|A, V|A, R|S, V|C | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int s = grid[p[n]] & 0x07; | |
int c = grid[p[n]] & 0x70; | |
for (int v = 0; v < 4; v++) { | |
for (int d = 1; ; d++) { | |
int tx = x + d * moves[v * 2 + 0]; | |
int ty = y + d * moves[v * 2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int i = ty * W + tx; | |
int ts = grid[i] & 0x07; | |
int tc = grid[i] & 0x70; | |
if ((!(n % 2) && s == ts) || ((n % 2) && c == tc)) { | |
p[n + 1] = i; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[17] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 5 | |
#define H 5 | |
static const signed char grid[] = { | |
+0, -24, +36, +1, +9, | |
+27, -5, -11, -11, +32, | |
+1, +9, -4, -21, -20, | |
-9, -1, -20, +9, +16, | |
-7, +24, -27, +12, +15 | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0 | |
}; | |
static int | |
isqrt(int v) | |
{ | |
if (v == 0) { | |
return 0; | |
} else if (v == 1) { | |
return 1; | |
} else if (v < 0) { | |
return -1; | |
} else { | |
int g = v / 2; | |
while (g * g != v) { | |
int n = (g + v / g) / 2; | |
if (abs(n - g) <= 1) | |
return n * n == v ? n : -1; | |
g = n; | |
} | |
return g; | |
} | |
} | |
static int | |
solve(int *p, int n, int bestn, int sum) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", grid[p[i]], " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
for (int v = 0; v < 4; v++) { | |
for (int d = 1; ; d++) { | |
int tx = x + d * moves[v * 2 + 0]; | |
int ty = y + d * moves[v * 2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int i = ty * W + tx; | |
int s = grid[i]; | |
if (isqrt(sum + s) != -1) { | |
p[n + 1] = i; | |
bestn = solve(p, n + 1, bestn, sum + s); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[13] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path), 0); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {NN, NE, EE, SE, SS, SW, WW, NW, RR}; | |
#define W 6 | |
#define H 6 | |
static const char grid[] = { | |
EE, SW, SE, SE, SS, SW, | |
EE, NE, RR, SE, EE, WW, | |
SE, NE, EE, SE, RR, SW, | |
EE, RR, SE, NE, SW, NW, | |
SE, SS, NN, RR, NE, SW, | |
NE, WW, WW, EE, NN, 0 | |
}; | |
static const int moves[] = { | |
+0, -1, | |
+1, -1, | |
+1, +0, | |
+1, +1, | |
+0, +1, | |
-1, +1, | |
-1, +0, | |
-1, -1 | |
}; | |
static int | |
solve(int *p, int n, int bestn, int dir) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]]; | |
if (v == RR) v = (dir + 4) % 8; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn, v); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[15] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path), 0); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 6 | |
#define H 6 | |
static const char grid[] = { | |
4, 4, 2, 3, 1, 0, | |
4, 3, 3, 3, 3, 1, | |
3, 4, 0, 2, 5, 1, | |
3, 3, 4, 0, 3, 3, | |
4, 2, 2, 4, 3, 1, | |
0, 3, 4, 4, 2, 0 | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
}; | |
static int | |
solve(int *p, int n, int j, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int d = grid[p[n]] ? grid[p[n]] : j; | |
for (int i = 0; i < 4; i++) { | |
int xx = x + d * moves[i * 2 + 0]; | |
int yy = y + d * moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, d, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[22] = {0}; | |
solve(path, 0, grid[0], sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {NN, SS, EE, WW, SE, NW, NE, SW}; | |
enum {B = 0x00, R = 0x10}; | |
#define W 6 | |
#define H 6 | |
static const char grid[] = { | |
B|EE, R|EE, B|SE, R|SE, R|SS, B|SW, | |
R|SE, R|EE, B|WW, R|SW, B|NN, R|SW, | |
R|EE, R|SE, R|NE, B|SS, B|NN, B|WW, | |
R|NN, R|NE, B|WW, R|EE, R|EE, R|NW, | |
R|EE, R|SW, R|SE, B|SS, R|NW, B|NN, | |
R|EE, B|NN, B|EE, B|NE, B|NE, 0 | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]] & 0x0f; | |
int t = n % 3 < 2; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int i = yy * W + xx; | |
int c = grid[i] >> 4; | |
if (i == W * H - 1 || c == t) { | |
/* No looping */ | |
int valid = 1; | |
for (int j = n - 2; valid && j >= 0; j -= 3) | |
if (p[j] == i) | |
valid = 0; | |
if (valid) { | |
p[n + 1] = i; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[28] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 8 | |
#define H 8 | |
static const char grid[] = { | |
2, 3, 3, 2, 3, 2, 3, 2, | |
3, 2, 2, 3, 2, 4, 2, 2, | |
3, 2, 3, 2, 3, 2, 3, 2, | |
2, 3, 3, 3, 2, 3, 2, 3, | |
3, 2, 3, 3, 3, 2, 3, 2, | |
2, 1, 2, 3, 2, 4, 2, 2, | |
1, 3, 3, 2, 3, 3, 2, 2, | |
2, 2, 2, 3, 2, 3, 2, 0 | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1, -1, -1, -1, +1, +1, -1, +1, +1 | |
}; | |
static int | |
solve(int *p, int n, char *seen, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int j = grid[p[n]]; | |
seen[p[n]] = 1; | |
for (int i = 0; i < 8; i++) { | |
int xx = x + j * moves[i * 2 + 0]; | |
int yy = y + j * moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int t = xx + yy * W; | |
if (!seen[t]) { | |
p[n + 1] = t; | |
bestn = solve(p, n + 1, seen, bestn); | |
} | |
} | |
} | |
seen[p[n]] = 0; | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
char seen[W * H] = {0}; | |
int path[8] = {0}; | |
solve(path, 0, seen, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
enum {A, B, C, X}; | |
#define W 7 | |
#define H 6 | |
static const char grid[] = { | |
A, B, B, C, B, A, B, | |
C, X, A, C, B, X, C, | |
A, A, B, A, C, B, A, | |
B, B, C, A, B, A, A, | |
C, X, B, C, A, X, C, | |
A, A, B, C, A, B, A | |
}; | |
static const signed char moves[] = { | |
+1, +0, +0, +1, -1, +0, +0, -1 | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int b = (last + 2) % 4; | |
int v = (n + 1) % 3; | |
for (int i = 0; i < 4; i++) { | |
if (i != b) { | |
int xx = x + moves[i * 2 + 0]; | |
int yy = y + moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int t = xx + yy * W; | |
int d = grid[t]; | |
if (d == X || d == v) { | |
p[n + 1] = t; | |
bestn = solve(p, n + 1, i, bestn); | |
} | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[34] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
enum {A, B, C, X}; | |
#define W 6 | |
#define H 6 | |
static const char grid[] = { | |
A, X, A, C, B, C, | |
C, X, X, X, X, B, | |
X, B, B, B, C, X, | |
X, B, B, A, B, C, | |
C, X, B, X, X, X, | |
A, X, X, C, A, C, | |
}; | |
static const signed char moves[] = { | |
+1, +0, +0, +1, -1, +0, +0, -1 | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int b = (last + 2) % 4; | |
int v = (n + 1) % 3; | |
for (int i = 0; i < 4; i++) { | |
if (i != b) { | |
int xx = x + moves[i * 2 + 0]; | |
int yy = y + moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int t = xx + yy * W; | |
int d = grid[t]; | |
if (d == X || d == v) { | |
p[n + 1] = t; | |
bestn = solve(p, n + 1, i, bestn); | |
} | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[45] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 4 | |
#define H 4 | |
enum {P, R, B, K, X}; | |
static const char grid[] = { | |
R, B, R, P, | |
B, P, B, K, | |
K, P, K, P, | |
R, R, B, X, | |
}; | |
static const signed char moves[] = { | |
0, 0, 8, 4, 16, 4, 24, 8, | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
-2, -1, -2, +1, +2, -1, +2, +1, | |
-1, -2, -1, +2, +1, -2, +1, +2, | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (grid[p[n]] == X) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int c = grid[p[n]] ? grid[p[n]] : last; | |
int off = moves[c * 2 + 0]; | |
int len = moves[c * 2 + 1]; | |
const signed char *m = moves + off; | |
for (int i = 0; i < len; i++) { | |
int xx = x + m[i * 2 + 0]; | |
int yy = y + m[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, c, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[15] = {0}; | |
solve(path, 0, grid[0], sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 5 | |
enum {R = 0x10, G = 0x20, B = 0x30, V = 0x40, Y = 0x50}; | |
enum {C = 0x01, D = 0x02, X = 0x03, S = 0x04, E = 0x05}; | |
static const char grid[] = { | |
R|C, B|D, B|E, G|S, G|C, | |
G|S, 0|0, B|E, V|C, R|X, | |
V|E, R|X, G|C, B|E, B|X, | |
Y|C, B|E, V|D, R|S, G|C, | |
B|E, 0|0, 0|0, R|X, Y|S | |
}; | |
static const int moves[] = {+0, -1, +0, +1, +1, +0, -1, +0}; | |
static int | |
solve(int *p, int n, int prev, long seen, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]] ? grid[p[n]] : prev; | |
int s = v & 0x0f; | |
int c = v & 0xf0; | |
for (int i = 0; i < 4; i++) { | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[i * 2 + 0]; | |
int yy = y + d * moves[i * 2 + 1]; | |
int j = yy * W + xx; | |
if (xx < 0 || xx >= W || yy < 0 || yy >= H) | |
break; | |
long bit = 1L << j; | |
if (grid[j] && (bit & seen)) | |
continue; | |
int t = grid[j]; | |
if (!t || (t & 0x0f) == s || (t & 0xf0) == c) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, v, seen | bit, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[31] = {0}; | |
solve(path, 0, 0, 1L << 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {S = 0x01, C = 0x02, D = 0x03, X = 0x04, P = 0x05}; | |
enum {V = 0x10, O = 0x20, Y = 0x30, R = 0x40, B = 0x50}; | |
#define W 5 | |
#define H 5 | |
static const char grid[] = { | |
V|S, O|D, Y|X, R|S, B|D, | |
V|D, B|X, O|D, Y|X, O|D, | |
B|X, O|D, R|C, O|P, R|D, | |
R|S, Y|D, O|C, O|P, O|D, | |
R|D, O|D, O|S, O|D, Y|X, | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int s = grid[p[n]] & 0x0f; | |
int c = grid[p[n]] & 0xf0; | |
int t = n % 6 < 3 ? 0 : 8; | |
for (int i = 0; i < 4; i++) { | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[t + i * 2 + 0]; | |
int yy = y + d * moves[t + i * 2 + 1]; | |
if (xx < 0 || xx >= W || yy < 0 || yy >= H) { | |
break; | |
} | |
int i = yy * W + xx; | |
int ts = grid[i] & 0x0f; | |
int tc = grid[i] & 0xf0; | |
if (s == ts || c == tc) { | |
p[n + 1] = i; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[11] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {NN, NE, EE, SE, SS, SW, WW, NW}; | |
#define W 7 | |
#define H 5 | |
static const char grid[] = { | |
SE, SE, EE, NN, EE, SS, NE, | |
EE, SW, WW, WW, WW, WW, WW, | |
SE, SW, SS, WW, SS, SS, EE, | |
SE, EE, SW, NN, NE, NN, NN, | |
WW, NN, SE, NW, NE, NW, 0 | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
static char mark[W * H]; | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int b = 1 << (n % 6); | |
if (mark[p[n]] & b) | |
return bestn; | |
mark[p[n]] ^= b; | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int a = grid[p[n]]; | |
int r = n / 3 % 2 ? -1 : 1; | |
for (int d = 1; ; d++) { | |
int xx = x + r * d * moves[a * 2 + 0]; | |
int yy = y + r * d * moves[a * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} else { | |
break; | |
} | |
} | |
mark[p[n]] ^= b; | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[23] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 5 | |
enum {R = 0x10, G = 0x20, B = 0x30, V = 0x40, Y = 0x50}; | |
enum {C = 0x01, D = 0x02, X = 0x03, P = 0x04, A = 0x05, S = 0x06}; | |
static const char grid[] = { | |
B|D, Y|A, V|C, B|C, R|P, | |
R|A, G|P, R|A, R|X, V|X, | |
V|P, R|A, V|P, R|A, B|A, | |
G|A, B|A, R|A, G|A, B|A, | |
V|S, R|A, B|S, B|P, Y|X, | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]]; | |
int s = v & 0x0f; | |
int c = v & 0xf0; | |
const int *m = moves + (n / 3 % 2) * 8; | |
for (int i = 0; i < 4; i++) { | |
for (int d = 1; ; d++) { | |
int xx = x + d * m[i * 2 + 0]; | |
int yy = y + d * m[i * 2 + 1]; | |
if (xx < 0 || xx >= W || yy < 0 || yy >= H) | |
break; | |
int t = grid[yy * W + xx]; | |
if ((t & 0x0f) == s || (t & 0xf0) == c) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[15] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define C 0x80 | |
enum {NN, NE, EE, SE, SS, SW, WW, NW}; | |
enum {B=0x10, R=0x20, P=0x40}; | |
#define W 6 | |
#define H 6 | |
static const unsigned char grid[] = { | |
0|B|EE, 0|R|SE, 0|R|NE, 0|B|EE, 0|R|EE, 0|P|SW, | |
0|R|SE, 0|B|WW, 0|B|SS, 0|P|NN, 0|B|SW, 0|B|NW, | |
0|P|NN, C|B|EE, 0|P|SW, 0|R|NW, 0|P|SW, 0|B|NN, | |
0|R|WW, 0|R|NW, 0|B|SS, 0|B|SE, 0|R|SS, 0|B|NW, | |
0|B|SE, 0|R|NE, C|R|EE, 0|P|NE, C|R|NE, 0|B|NE, | |
0|B|NE, 0|R|WW, 0|R|NE, 0|P|SW, 0|R|EE, 0 | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int r, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]] & 0x0f; | |
int c = grid[p[n]] & 0x70; | |
if (r) v = (v + 4) % 8; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
static char seen[2][W*H]; | |
int i = yy * W + xx; | |
int cc = grid[i] & 0x70; | |
if (!seen[r][i] && cc != c) { | |
int rr = grid[i] & 0x80 ? !r : r; | |
p[n + 1] = i; | |
seen[r][i] = 1; | |
bestn = solve(p, n + 1, rr, bestn); | |
seen[r][i] = 0; | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[23] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 6 | |
#define H 6 | |
enum {P, R, B, K}; | |
enum {D, L = 0x10}; | |
static const char grid[] = { | |
D|B, L|K, L|K, L|B, D|K, D|B, | |
L|K, D|K, L|B, L|B, D|K, D|R, | |
D|K, L|K, L|K, L|K, D|K, D|K, | |
L|B, L|K, L|K, L|K, D|K, L|K, | |
L|K, D|B, D|B, L|B, D|K, D|K, | |
L|B, L|B, L|K, D|K, L|K, L|K | |
}; | |
static const signed char moves[] = { | |
0, 0, 8, 4, 16, 4, 24, 8, | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
-2, -1, -2, +1, +2, -1, +2, +1, | |
-1, -2, -1, +2, +1, -2, +1, +2, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int g = (n+1) / 2 % 2; | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]] & 0x0f; | |
int off = moves[v * 2 + 0]; | |
int len = moves[v * 2 + 1]; | |
const signed char *m = moves + off; | |
for (int i = 0; i < len; i++) { | |
int xx = x + m[i * 2 + 0]; | |
int yy = y + m[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int t = yy * W + xx; | |
if (grid[t] >> 4 == g) { | |
p[n + 1] = t; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[27] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define H 5 | |
#define W 5 | |
static const signed char grid[] = { | |
+2, -1, -1, -2, +1, | |
-1, +9, +1, +9, -1, | |
-2, +0, +1, +1, -1, | |
+0, +9, +1, +9, +1, | |
-1, -1, -1, -1, +0 | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1 | |
}; | |
static int | |
solve(int *p, int n, int v, int bestn) | |
{ | |
if (p[n - 1] == W * H - 1) { | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n - 1] % W; | |
int y = p[n - 1] / W; | |
for (int i = 0; i < 4; i++) { | |
if (x % 2 == 1 && i > 1) continue; | |
if (y % 2 == 1 && i < 2) continue; | |
int tx = x + moves[i * 2 + 0] * v; | |
int ty = y + moves[i * 2 + 1] * v; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int t = ty * W + tx; | |
if (grid[t] + v >= 0) { | |
p[n] = t; | |
bestn = solve(p, n + 1, grid[t] + v, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[26] = {0}; | |
solve(path, 1, grid[0], sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
enum {A, B, C, X}; | |
#define W 6 | |
#define H 5 | |
static const char grid[] = { | |
A, B, X, X, A, X, | |
C, C, C, X, X, A, | |
X, X, C, B, C, X, | |
X, A, C, X, B, A, | |
X, X, B, X, B, X | |
}; | |
static const signed char moves[] = { | |
+1, +0, +0, +1, -1, +0, +0, -1 | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int b = (last + 2) % 4; | |
int v = (n + 1) % 3; | |
for (int i = 0; i < 4; i++) { | |
if (i != b) { | |
int xx = x + moves[i * 2 + 0]; | |
int yy = y + moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int t = xx + yy * W; | |
int d = grid[t]; | |
if (d == X || d == v) { | |
p[n + 1] = t; | |
bestn = solve(p, n + 1, i, bestn); | |
} | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[24] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 7 | |
#define H 5 | |
enum {NN, NE, EE, SE, SS, SW, WW, NW}; | |
static const char grid[] = { | |
SE, SE, EE, NN, EE, SE, SS, | |
SE, EE, EE, WW, WW, WW, EE, | |
SS, WW, WW, NN, WW, WW, EE, | |
NN, WW, NE, NN, WW, WW, EE, | |
SS, NN, WW, NN, SS, WW, 0 | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]]; | |
if (n % 6 > 2) v = (v + 4) % 8; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[23] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 7 | |
#define H 7 | |
enum {NN, NE, EE, SE, SS, SW, WW, NW, XX}; | |
static const char grid[] = { | |
XX, SW, NW, NW, SE, NE, XX, | |
SE, SE, SW, SW, NE, SS, NW, | |
NE, NW, SW, SE, NE, NW, NE, | |
SW, NE, NE, NN, SW, SW, WW, | |
NE, NE, SW, NE, NE, NE, SW, | |
WW, SS, NW, SW, SE, NW, NE, | |
XX, NW, SE, NE, SE, SW, XX | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (grid[p[n]] == XX) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]]; | |
if (n % 2) v = (v + 4) % 8; | |
for (int d = 1; ; d++) { | |
int xx = x + d * moves[v * 2 + 0]; | |
int yy = y + d * moves[v * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = yy * W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[12] = {24}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 5 | |
#define H 5 | |
static const char grid[] = { | |
0, 0, 0, 0, 0, | |
0, 0, 2, 0, 1, | |
0, 1, 0, 0, 2, | |
1, 0, 0, 1, 1, | |
1, 0, 2, 2, 0 | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
}; | |
static int | |
solve(int *p, int n, int d, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
d += grid[p[n]]; | |
for (int i = 0; i < 4; i++) { | |
int xx = x + d * moves[i * 2 + 0]; | |
int yy = y + d * moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
bestn = solve(p, n + 1, d, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[16] = {0}; | |
solve(path, 0, 1, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define C 0x80 | |
enum {N=0x01, Q=0x02, X=0x03, D=0x04, T=0x05, S=0x06}; | |
enum {R=0x10, Y=0x20, B=0x30, V=0x40, O=0x50, G=0x60}; | |
#define W 6 | |
#define H 6 | |
static const unsigned char grid[] = { | |
0|N|V, C|N|Y, 0|X|Y, C|T|Y, C|T|B, C|N|B, | |
C|Q|V, 0|S|Y, C|S|G, 0|X|V, C|D|B, 0|X|R, | |
0|T|Y, 0|T|Y, C|N|V, C|T|V, 0|T|R, 0|D|V, | |
C|D|R, C|Q|V, C|D|G, 0|D|R, C|D|O, C|D|B, | |
C|Q|R, 0|S|B, C|Q|R, 0|X|Y, C|T|V, C|X|R, | |
C|Q|R, 0|S|R, C|D|B, 0|Q|Y, C|S|Y, 0|X|O | |
}; | |
static const int moves[] = { | |
+0, -1, +0, +1, +1, +0, -1, +0, | |
+1, +1, -1, -1, +1, -1, -1, +1, | |
}; | |
static int | |
solve(int *p, int n, int m, int bestn) | |
{ | |
static char seen[W*H][W*H]; | |
if (p[n] == W * H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int s = grid[p[n]] & 0x07; | |
int c = grid[p[n]] & 0x70; | |
const int *o = moves + 8*m; | |
for (int v = 0; v < 4; v++) { | |
for (int d = 1; ; d++) { | |
int tx = x + d*o[v*2 + 0]; | |
int ty = y + d*o[v*2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int i = ty*W + tx; | |
int ts = grid[i] & 0x07; | |
int tc = grid[i] & 0x70; | |
int to = grid[i] & 0x80; | |
int nm = to ? !m : m; | |
if (!seen[p[n]][i] && ((s == ts) || (c == tc))) { | |
p[n+1] = i; | |
seen[p[n]][i] = 1; | |
bestn = solve(p, n + 1, nm, bestn); | |
seen[p[n]][i] = 0; | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[33] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {G=0x10, B=0x20, R=0x30, V=0x40}; | |
enum {D=0x01, S=0x02, C=0x03, P=0x04, X=0x05}; | |
#define H 5 | |
#define W 5 | |
static const signed char grid[] = { | |
G|D, G|C, G|C, B|C, B|D, | |
B|S, 0, B|C, 0, R|S, | |
B|D, R|D, R|C, R|X, R|C, | |
V|D, 0, V|C, 0, B|D, | |
B|X, B|X, V|C, B|C, R|P, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n - 1] == W * H - 1) { | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n - 1] % W; | |
int y = p[n - 1] / W; | |
int m = n % 2 ? 0x0f : 0xf0; | |
for (int i = 0; i < 4; i++) { | |
if (x % 2 == 1 && i > 1) continue; | |
if (y % 2 == 1 && i < 2) continue; | |
for (int v = 1; ; v++) { | |
int tx = x + v * moves[i * 2 + 0]; | |
int ty = y + v * moves[i * 2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int t = ty * W + tx; | |
if ((grid[t] & m) == (grid[p[n-1]] & m)) { | |
p[n] = t; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[16] = {0}; | |
solve(path, 1, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
enum {A, B, C, X}; | |
#define W 5 | |
#define H 5 | |
static const char grid[] = { | |
A, X, X, C, X, | |
X, B, X, X, C, | |
C, B, A, B, X, | |
B, X, C, C, C, | |
X, X, X, B, X | |
}; | |
static const signed char moves[] = { | |
+1, +0, +0, +1, -1, +0, +0, -1 | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (p[n] == H * W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int b = (last + 2) % 4; | |
int v = (n + 1) % 3; | |
for (int i = 0; i < 4; i++) { | |
if (i != b) { | |
int xx = x + moves[i * 2 + 0]; | |
int yy = y + moves[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
int t = xx + yy * W; | |
int d = grid[t]; | |
if (d == X || d == v) { | |
p[n + 1] = t; | |
bestn = solve(p, n + 1, i, bestn); | |
} | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[33] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 6 | |
#define H 6 | |
enum {P, R, B, K, X}; | |
static const char grid[] = { | |
K, P, R, P, R, B, | |
P, R, B, R, B, B, | |
B, B, R, R, P, B, | |
P, R, B, P, B, R, | |
P, B, R, B, K, P, | |
P, K, P, B, B, X, | |
}; | |
static const signed char moves[] = { | |
0, 0, 8, 4, 16, 4, 24, 8, | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
-2, -1, -2, +1, +2, -1, +2, +1, | |
-1, -2, -1, +2, +1, -2, +1, +2, | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (grid[p[n]] == X) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int c = grid[p[n]] ? grid[p[n]] : last; | |
int off = moves[c * 2 + 0]; | |
int len = moves[c * 2 + 1]; | |
const signed char *m = moves + off; | |
for (int i = 0; i < len; i++) { | |
int xx = x + m[i * 2 + 0]; | |
int yy = y + m[i * 2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n + 1] = xx + yy * W; | |
int loop = 0; | |
if (grid[p[n + 1]]) | |
for (int j = 0; !loop && j < n; j++) | |
if (p[j] == p[n + 1]) | |
loop = 1; | |
if (!loop) | |
bestn = solve(p, n + 1, c, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[30] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {D, S, E, C}; | |
#define H 5 | |
#define W 5 | |
static const signed char grid[] = { | |
D, D, C, D, D, | |
C, S, C, S, D, | |
D, S, C, E, D, | |
E, S, E, E, E, | |
D, S, D, D, D, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n - 1] == W * H - 1) { | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n-1] % W; | |
int y = p[n-1] / W; | |
for (int i = 0; i < 4; i++) { | |
for (int v = 1; ; v++) { | |
int tx = x + v*moves[i*2+0]; | |
int ty = y + v*moves[i*2+1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
p[n] = ty*W + tx; | |
if ((n < 1 || grid[p[n-1]] != grid[p[n]]) && | |
(n < 2 || grid[p[n-2]] != grid[p[n]])) { | |
bestn = solve(p, n + 1, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[13] = {0}; | |
solve(path, 1, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {C=1, V, A, X}; | |
#define H 7 | |
#define W 7 | |
static const signed char grid[] = { | |
0, V, V, V, A, A, C, | |
V, A, A, V, A, 0, C, | |
A, 0, A, 0, C, V, C, | |
V, V, V, X, V, A, 0, | |
A, 0, 0, A, C, C, C, | |
A, 0, 0, A, A, 0, A, | |
A, C, A, V, C, A, C, | |
}; | |
static const signed char moves[] = { | |
+1, +0, +0, +1, -1, +0, +0, -1, | |
}; | |
static int | |
solve(int *p, int n, int d, int bestn) | |
{ | |
if (p[n - 1] == W * H / 2) { | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n-1] % W; | |
int y = p[n-1] / W; | |
for (int v = 1; ; v++) { | |
int tx = x + v*moves[d*2+0]; | |
int ty = y + v*moves[d*2+1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int ti = ty*W + tx; | |
int g = grid[ti]; | |
if (!g || (d%2 && g == V)) continue; | |
p[n] = ti; | |
bestn = solve(p, n + 1, (d + g + d%2*2) % 4, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[30] = {0}; | |
solve(path, 1, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {D=1, S, C}; | |
#define BEG 3 | |
#define END 45 | |
#define W 7 | |
#define H 7 | |
static const unsigned char grid[] = { | |
0, 0, 0, D, 0, 0, 0, | |
0, 0, D, D, S, 0, 0, | |
0, S, C, D, D, D, 0, | |
D, S, D, C, D, C, D, | |
0, D, C, D, D, D, 0, | |
0, 0, D, D, S, 0, 0, | |
0, 0, 0, D, 0, 0, 0, | |
}; | |
static const int moves[] = { | |
+0, +1, -1, +1, -1, +0, -1, -1, +0, -1, +1, -1, +1, +0, +1, +1, | |
}; | |
static int | |
solve(int *p, int n, int d, int bestn) | |
{ | |
if (p[n] == END) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int a = grid[p[n]]; | |
int b = n ? grid[p[n-1]] : 0; | |
for (int i = 0; i < 8; i++) { | |
if (i == (d + 4) % 8) continue; // no u-turns | |
for (int v = 1; ; v++) { | |
int tx = x + v*moves[i*2 + 0]; | |
int ty = y + v*moves[i*2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int ti = ty*W + tx; | |
int c = grid[ti]; | |
if (c && c != a && c != b) { | |
p[n+1] = ti; | |
bestn = solve(p, n+1, i, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[10] = {BEG}; | |
solve(path, 0, 0, sizeof(path)/sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define H 5 | |
#define W 5 | |
static const signed char grid[] = { | |
+0, +2, -1, -1, -1, | |
+2, -1, +0, +1, -3, | |
+0, +0, +1, -1, -1, | |
-1, -1, +0, -1, +2, | |
-1, +0, -1, -1, +0, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1 | |
}; | |
static int | |
solve(int *p, int n, int v, int bestn) | |
{ | |
if (p[n - 1] == W*H - 1) { | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n-1] % W; | |
int y = p[n-1] / W; | |
for (int i = 0; i < 4; i++) { | |
int tx = x + v*moves[i*2 + 0]; | |
int ty = y + v*moves[i*2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int t = ty * W + tx; | |
if (grid[t] + v >= 0) { | |
p[n] = t; | |
bestn = solve(p, n + 1, grid[t] + v, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[12] = {0}; | |
solve(path, 1, 3, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#define W 7 | |
#define H 7 | |
static const char grid[] = { | |
3, 1, 3, 4, 3, 4, 0, | |
2, 4, 1, 2, 1, 3, 0, | |
1, 1, 1, 4, 3, 4, 0, | |
2, 1, 1, 2, 1, 2, 0, | |
1, 4, 3, 1, 4, 4, 0, | |
3, 2, 4, 2, 1, 2, 0, | |
3, 1, 1, 4, 1, 4, 0, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] % W == W - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int d = grid[p[n]]; | |
for (int i = 0; i < 4; i++) { | |
int xx = x + d*moves[i*2 + 0]; | |
int yy = y + d*moves[i*2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n+1] = xx + yy*W; | |
bestn = solve(p, n+1, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[19] = {21}; | |
solve(path, 0, sizeof(path)/sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {G=0x10, B=0x20, R=0x30, V=0x40, Y=0x50, K=0x60}; | |
enum {D=0x01, S=0x02, C=0x03, P=0x04, X=0x05, A=0x06}; | |
#define H 5 | |
#define W 5 | |
static const signed char grid[] = { | |
B|C, K|A, R|A, G|C, K|C, | |
R|P, K|P, B|D, B|A, R|A, | |
V|C, V|X, Y|X, G|X, K|P, | |
Y|S, K|C, Y|P, R|A, R|P, | |
G|S, R|C, R|D, B|D, G|X, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n - 1] == W * H - 1) { | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n - 1] % W; | |
int y = p[n - 1] / W; | |
int m = n % 2 ? 0x0f : 0xf0; | |
for (int i = 0; i < 4; i++) { | |
for (int v = 1; ; v++) { | |
int tx = x + v*moves[i*2 + 0]; | |
int ty = y + v*moves[i*2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int t = ty * W + tx; | |
if ((grid[t] & m) == (grid[p[n-1]] & m)) { | |
p[n] = t; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[14] = {0}; | |
solve(path, 1, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 5 | |
#define T 13 | |
static const struct { | |
enum { M, A } op; | |
int value; | |
} grid[] = { | |
{M, +0}, {A, +1}, {M, +2}, {A, +2}, {A, +0}, | |
{A, +1}, {M, +4}, {A, +2}, {A, -2}, {A, +2}, | |
{M, +3}, {M, +2}, {A, +2}, {M, +2}, {M, +3}, | |
{A, +2}, {A, +2}, {A, -2}, {M, +4}, {A, -3}, | |
{A, -2}, {A, -2}, {M, +2}, {A, +1}, {A, +1}, | |
}; | |
static const int moves[] = {-1, +0, +1, +0, +0, -1, +0, +1}; | |
static int | |
solve(int *p, int n, int v, int bestn) | |
{ | |
switch (grid[p[n]].op) { | |
case M: v *= grid[p[n]].value; break; | |
case A: v += grid[p[n]].value; break; | |
} | |
if (p[n] == H*W - 1 && v == T) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (p[n] != H*W - 1 && n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
for (int i = 0; i < 4; i++) { | |
int xx = x + moves[i*2 + 0]; | |
int yy = y + moves[i*2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n+1] = xx + yy * W; | |
bestn = solve(p, n+1, v, bestn); | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[15] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {G=0x10, B=0x20, R=0x30, V=0x40, Y=0x50, O=0x60}; | |
enum {D=0x01, S=0x02, C=0x03, E=0x04}; | |
#define H 6 | |
#define W 6 | |
static const signed char grid[] = { | |
E|Y, D|G, D|O, D|V, C|V, S|O, | |
C|O, C|G, S|G, E|B, C|R, C|G, | |
E|R, C|B, E|V, C|R, D|B, S|O, | |
D|G, E|R, D|G, E|B, S|V, C|B, | |
D|G, E|G, C|G, S|R, E|O, S|B, | |
D|B, C|V, E|G, S|B, C|G, D|R, | |
}; | |
static const signed char moves[] = { | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n-1] == W*H - 1) { | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n-1] % W; | |
int y = p[n-1] / W; | |
int m = n % 2 ? 0x0f : 0xf0; | |
for (int i = 0; i < 8; i++) { | |
for (int v = 1; ; v++) { | |
int tx = x + v*moves[i*2 + 0]; | |
int ty = y + v*moves[i*2 + 1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int t = ty * W + tx; | |
if ((grid[t] & m) == (grid[p[n-1]] & m)) { | |
p[n] = t; | |
bestn = solve(p, n + 1, bestn); | |
} | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[23] = {0}; | |
solve(path, 1, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 5 | |
enum {NN, NE, EE, SE, SS, SW, WW, NW}; | |
static const char grid[] = { | |
SS, SE, SW, SS, WW, | |
SE, EE, NN, SW, EE, | |
SS, WW, NN, EE, WW, | |
NN, NN, SW, SW, NN, | |
SE, NE, EE, SE, 0, | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int bestn) | |
{ | |
if (p[n] == W*H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]]; | |
for (int d = 1; ; d++) { | |
int xx = x + d*moves[v*2 + 0]; | |
int yy = y + d*moves[v*2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n+1] = yy*W + xx; | |
bestn = solve(p, n + 1, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[18] = {0}; | |
solve(path, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 4 | |
#define H 4 | |
enum {NN, NE, EE, SE, SS, SW, WW, NW}; | |
static const char grid[] = { | |
EE, SW, SS, SW, | |
SE, SE, NN, WW, | |
SE, EE, NW, NN, | |
NN, WW, WW, 0, | |
}; | |
static const int moves[] = { | |
+0, -1, +1, -1, +1, +0, +1, +1, +0, +1, -1, +1, -1, +0, -1, -1 | |
}; | |
static int | |
solve(int *p, int n, int m, int bestn) | |
{ | |
if (p[n] == W*H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int v = grid[p[n]]; | |
for (int d = m ? m : 1; ; d += m ? 3 : 1) { | |
int xx = x + d*moves[v*2 + 0]; | |
int yy = y + d*moves[v*2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n+1] = yy*W + xx; | |
bestn = solve(p, n + 1, m ? 0 : d, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[12] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 6 | |
#define H 6 | |
enum {P, R, B, K, Q, X}; | |
static const char grid[] = { | |
Q, B, K, B, K, P, | |
B, P, B, R, P, P, | |
K, B, R, B, K, P, | |
P, R, B, R, P, K, | |
P, B, R, B, P, B, | |
P, K, P, K, B, X, | |
}; | |
static const signed char moves[] = { | |
0, 0, 10, 4, 18, 4, 26, 8, 42, 8, | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
-2, -1, -2, +1, +2, -1, +2, +1, | |
-1, -2, -1, +2, +1, -2, +1, +2, | |
-1, +0, +1, +0, +0, -1, +0, +1, | |
-1, -1, +1, +1, -1, +1, +1, -1, | |
}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (grid[p[n]] == X) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int c = grid[p[n]] ? grid[p[n]] : last; | |
int off = moves[c*2 + 0]; | |
int len = moves[c*2 + 1]; | |
const signed char *m = moves + off; | |
for (int i = 0; i < len; i++) { | |
int xx = x + m[i*2 + 0]; | |
int yy = y + m[i*2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n+1] = xx + yy*W; | |
int loop = 0; | |
if (grid[p[n+1]]) { | |
for (int j = 0; !loop && j < n; j++) { | |
if (p[j] == p[n+1]) { | |
loop = 1; | |
} | |
} | |
} | |
if (!loop) { | |
bestn = solve(p, n+1, c, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[25] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define W 5 | |
#define H 4 | |
enum {D, U, V, Z}; | |
static const char grid[] = { | |
D, Z, U, V, Z, | |
V, U, U, U, V, | |
D, D, V, U, Z, | |
D, U, V, Z, 0, | |
}; | |
static const int moves[] = {+1, +1, +1, -1, +0, +1, +1, +0}; | |
static int | |
solve(int *p, int n, int last, int bestn) | |
{ | |
if (p[n] == W*H - 1) { | |
for (int i = 0; i <= n; i++) | |
printf("%d%c", p[i] + 1, " \n"[i == n]); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
int a = n&1 ? last : 1; | |
int b = n&1 ? last : 4; | |
int c = grid[p[n]]; | |
for (int d = a; d <= b; d++) { | |
for (int v = -1; v <= +1; v += 2) { | |
int xx = x + v*d*moves[c*2 + 0]; | |
int yy = y + v*d*moves[c*2 + 1]; | |
if (xx >= 0 && xx < W && yy >= 0 && yy < H) { | |
p[n+1] = xx + yy*W; | |
bestn = solve(p, n+1, d, bestn); | |
} | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[26] = {0}; | |
solve(path, 0, 0, sizeof(path) / sizeof(*path)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
enum {H, D, V, U, X}; | |
#define H 7 | |
#define W 7 | |
static const signed char grid[] = { | |
D, U, V, H, U, U, D, | |
U, H, U, H, H, D, H, | |
U, H, H, H, D, D, H, | |
V, V, V, X, V, V, H, | |
V, V, D, U, V, V, V, | |
D, D, H, H, U, V, D, | |
D, U, H, H, U, U, X, | |
}; | |
static const signed char moves[] = { | |
+1, +0, +0, +1, -1, +0, +0, -1, | |
}; | |
static int | |
solve(int *p, int n, int d, int bestn) | |
{ | |
if (p[n] == W*H - 1) { | |
for (int i = 0; i < n; i++) | |
printf("%d%c", 1 + p[i], i < n - 1 ? ' ' : '\n'); | |
bestn = n; | |
} else if (n < bestn - 1) { | |
int x = p[n] % W; | |
int y = p[n] / W; | |
for (int v = 1; ; v++) { | |
int tx = x + v*moves[d*2+0]; | |
int ty = y + v*moves[d*2+1]; | |
if (tx >= 0 && tx < W && ty >= 0 && ty < H) { | |
int ti = ty*W + tx; | |
int td = d; | |
switch (grid[ti]) { | |
case H: if (d%2 == 0) continue; td += 2; break; | |
case V: if (d%2 == 1) continue; td += 2; break; | |
case D: td += 1 + d%2*2; break; | |
case U: td += 3 + d%2*2; break; | |
} | |
p[n+1] = ti; | |
bestn = solve(p, n+1, td%4, bestn); | |
} else { | |
break; | |
} | |
} | |
} | |
return bestn; | |
} | |
int | |
main(void) | |
{ | |
int path[14] = {24}; | |
solve(path, 0, 1, sizeof(path) / sizeof(*path)); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment