厉害
格式化一下代码，方便阅读
程序代码：
格式化一下代码，方便阅读
程序代码：
#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#pragma pack(1)
typedef struct tagCUBE
{
struct tagCUBE* parent;
char f[3][3];
char b[3][3];
char u[3][3];
char d[3][3];
char l[3][3];
char r[3][3];
char op;
} CUBE;
#pragma pack()
typedef struct
{
int stride;
char* buffer;
} LINEITEM;
static void line_rotate90(LINEITEM item[5])
{
int i, j;
for (i = 0; i < 5; i++)
{
int dst_idx = (i + 0) % 5;
int src_idx = (i + 1) % 5;
char* dst_buf = item[dst_idx].buffer;
char* src_buf = item[src_idx].buffer;
int dst_stride = item[dst_idx].stride;
int src_stride = item[src_idx].stride;
for (j = 0; j < 3; j++)
{
*dst_buf = *src_buf;
dst_buf += dst_stride;
src_buf += src_stride;
}
}
}
static void surface_rotate90(char buf[3][3])
{
char tmp[3][3];
int i, j;
memcpy(tmp, buf, sizeof(tmp));
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
buf[i][j] = tmp[3 - j - 1][i];
}
}
}
static void cube_init(CUBE* c)
{
memset(c->f, 'w', sizeof(c->f));
memset(c->b, 'y', sizeof(c->b));
memset(c->u, 'b', sizeof(c->u));
memset(c->d, 'g', sizeof(c->d));
memset(c->l, 'o', sizeof(c->l));
memset(c->r, 'r', sizeof(c->r));
}
static void cube_f(CUBE* c)
{
char temp[3];
LINEITEM lines[5] =
{
{ 1, temp },
{ 3, &(c->l[0][2]) },
{ 1, &(c->d[0][0]) },
{-3, &(c->r[2][0]) },
{-1, &(c->u[2][2]) },
};
line_rotate90(lines);
surface_rotate90(c->f);
}
static void cube_b(CUBE* c)
{
char temp[3];
LINEITEM lines[5] =
{
{ 1, temp },
{ 3, &(c->r[0][2]) },
{-1, &(c->d[2][2]) },
{-3, &(c->l[2][0]) },
{ 1, &(c->u[0][0]) },
};
line_rotate90(lines);
surface_rotate90(c->b);
}
static void cube_u(CUBE* c)
{
char temp[3];
LINEITEM lines[5] =
{
{ 1, temp },
{ 1, &(c->l[0][0]) },
{ 1, &(c->f[0][0]) },
{ 1, &(c->r[0][0]) },
{ 1, &(c->b[0][0]) },
};
line_rotate90(lines);
surface_rotate90(c->u);
}
static void cube_d(CUBE* c)
{
char temp[3];
LINEITEM lines[5] =
{
{ 1, temp },
{ 1, &(c->b[2][0]) },
{ 1, &(c->r[2][0]) },
{ 1, &(c->f[2][0]) },
{ 1, &(c->l[2][0]) },
};
line_rotate90(lines);
surface_rotate90(c->d);
}
static void cube_l(CUBE* c)
{
char temp[3];
LINEITEM lines[5] =
{
{ 1, temp },
{ 3, &(c->d[0][0]) },
{ 3, &(c->f[0][0]) },
{ 3, &(c->u[0][0]) },
{-3, &(c->b[2][2]) },
};
line_rotate90(lines);
surface_rotate90(c->l);
}
static void cube_r(CUBE* c)
{
char temp[3];
LINEITEM lines[5] =
{
{ 1, temp },
{ 3, &(c->u[0][2]) },
{ 3, &(c->f[0][2]) },
{ 3, &(c->d[0][2]) },
{-3, &(c->b[2][0]) },
};
line_rotate90(lines);
surface_rotate90(c->r);
}
enum
{
CUBE_OP_F,
CUBE_OP_B,
CUBE_OP_U,
CUBE_OP_D,
CUBE_OP_L,
CUBE_OP_R,
};
static void (*g_op_tab[])(CUBE* c) = { cube_f, cube_b, cube_u, cube_d, cube_l, cube_r };
static void cube_op(CUBE* c, int op)
{
(g_op_tab[op])(c);
}
static void cube_rand(CUBE* c, int n)
{
while (n-- > 0)
{
cube_op(c, rand() % 6);
}
}
static void cube_render(CUBE* c)
{
char buffer[9][12] = {0};
int i, j;
HANDLE h = GetStdHandle(STD_OUTPUT_HANDLE);
WORD wOldColorAttrs;
CONSOLE_SCREEN_BUFFER_INFO csbiInfo;
// save the current color
GetConsoleScreenBufferInfo(h, &csbiInfo);
wOldColorAttrs = csbiInfo.wAttributes;
for (i = 0; i < 3; i++) for (j = 0; j < 3; j++)
{
buffer[3 + i][3 + j] = c->f[i][j];
}
for (i = 0; i < 3; i++) for (j = 0; j < 3; j++)
{
buffer[3 + i][9 + j] = c->b[i][j];
}
for (i = 0; i < 3; i++) for (j = 0; j < 3; j++)
{
buffer[0 + i][3 + j] = c->u[i][j];
}
for (i = 0; i < 3; i++) for (j = 0; j < 3; j++)
{
buffer[6 + i][3 + j] = c->d[i][j];
}
for (i = 0; i < 3; i++) for (j = 0; j < 3; j++)
{
buffer[3 + i][0 + j] = c->l[i][j];
}
for (i = 0; i < 3; i++) for (j = 0; j < 3; j++)
{
buffer[3 + i][6 + j] = c->r[i][j];
}
for (i = 0; i < 9; i++)
{
for (j = 0; j < 12; j++)
{
switch (buffer[i][j])
{
case 'w':
case 'W':
SetConsoleTextAttribute(h, FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
break;
case 'y':
case 'Y':
SetConsoleTextAttribute(h, FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN);
break;
case 'b':
case 'B':
SetConsoleTextAttribute(h, FOREGROUND_INTENSITY | FOREGROUND_BLUE);
break;
case 'g':
case 'G':
SetConsoleTextAttribute(h, FOREGROUND_INTENSITY | FOREGROUND_GREEN);
break;
case 'o':
case 'O':
SetConsoleTextAttribute(h, FOREGROUND_RED | FOREGROUND_BLUE);
break;
case 'r':
case 'R':
SetConsoleTextAttribute(h, FOREGROUND_INTENSITY | FOREGROUND_RED);
break;
}
printf(buffer[i][j] ? "\2 " : " ");
}
printf("\n");
}
// restore the original color
SetConsoleTextAttribute(h, wOldColorAttrs);
}
static int cube_check_fcross0(CUBE* cube)
{
int checklist[][2] =
{
{ cube->f[1][1], cube->f[0][1] },
{ cube->f[1][1], cube->f[1][0] },
{ cube->f[1][1], cube->f[1][2] },
{ cube->f[1][1], cube->f[2][1] },
};
int value = 0, i;
for (i = 0; i < 4; i++)
{
value += (checklist[i][0] == checklist[i][1]);
}
return value;
}
static int cube_check_fcross1(CUBE* cube)
{
int checklist[][2] =
{
{ cube->l[1][1], cube->l[1][2] },
{ cube->u[1][1], cube->u[2][1] },
{ cube->r[1][1], cube->r[1][0] },
{ cube->d[1][1], cube->d[0][1] },
};
int value = 0, i;
for (i = 0; i < 4; i++)
{
value += (checklist[i][0] == checklist[i][1]);
}
return value;
}
static int cube_check_fcorners(CUBE* cube)
{
int checklist[][3][2] =
{
{
{ cube->f[1][1], cube->f[0][0] },
{ cube->l[1][1], cube->l[0][2] },
{ cube->u[1][1], cube->u[2][0] },
},
{
{ cube->f[1][1], cube->f[0][2] },
{ cube->u[1][1], cube->u[2][2] },
{ cube->r[1][1], cube->r[0][0] },
},
{
{ cube->f[1][1], cube->f[2][0] },
{ cube->l[1][1], cube->l[2][2] },
{ cube->d[1][1], cube->d[0][0] },
},
{
{ cube->f[1][1], cube->f[2][2] },
{ cube->r[1][1], cube->r[2][0] },
{ cube->d[1][1], cube->d[0][2] },
},
};
int value = 0, i, j;
for (j = 0; j < 4; j++)
{
value++;
for (i = 0; i < 3; i++)
{
if (checklist[j][i][0] != checklist[j][i][1])
{
value--;
break;
}
}
}
return value;
}
static int cube_check_medges(CUBE* cube)
{
int checklist[][2][2] =
{
{
{ cube->l[1][1], cube->l[0][1] },
{ cube->u[1][1], cube->u[1][0] },
},
{
{ cube->u[1][1], cube->u[1][2] },
{ cube->r[1][1], cube->r[0][1] },
},
{
{ cube->l[1][1], cube->l[2][1] },
{ cube->d[1][1], cube->d[1][0] },
},
{
{ cube->r[1][1], cube->r[2][1] },
{ cube->d[1][1], cube->d[1][2] },
},
};
int value = 0, i, j;
for (j = 0; j < 4; j++)
{
value++;
for (i = 0; i < 2; i++)
{
if (checklist[j][i][0] != checklist[j][i][1])
{
value--;
break;
}
}
}
return value;
}
static int cube_check_bcross(CUBE* cube)
{
int checklist[][2][2] =
{
{
{ cube->b[1][1], cube->b[0][1] },
{ cube->b[1][1], cube->b[2][1] },
},
{
{ cube->b[1][1], cube->b[1][0] },
{ cube->b[1][1], cube->b[1][2] },
},
};
int value = 0, i, j;
for (j = 0; j < 2; j++)
{
value += 2;
for (i = 0; i < 2; i++)
{
if (checklist[j][i][0] != checklist[j][i][1])
{
value -= 2;
break;
}
}
}
return value;
}
static int cube_check_bsurface(CUBE* cube)
{
int checklist[][2] =
{
{ cube->b[1][1], cube->b[0][0] },
{ cube->b[1][1], cube->b[0][2] },
{ cube->b[1][1], cube->b[2][0] },
{ cube->b[1][1], cube->b[2][2] },
};
int value = 0, i;
for (i = 0; i < 4; i++)
{
value += (checklist[i][0] == checklist[i][1]);
}
if (value == 2)
{
value = 0;
}
return value;
}
static int cube_check_bcorners(CUBE* cube)
{
int checklist[][3][2] =
{
{
{ cube->b[1][1], cube->b[0][2] },
{ cube->l[1][1], cube->l[0][0] },
{ cube->u[1][1], cube->u[0][0] },
},
{
{ cube->b[1][1], cube->b[0][0] },
{ cube->u[1][1], cube->u[0][2] },
{ cube->r[1][1], cube->r[0][2] },
},
{
{ cube->b[1][1], cube->b[2][0] },
{ cube->r[1][1], cube->r[2][2] },
{ cube->d[1][1], cube->d[2][2] },
},
{
{ cube->b[1][1], cube->b[2][2] },
{ cube->l[1][1], cube->l[2][0] },
{ cube->d[1][1], cube->d[2][0] },
},
};
int returned[4] = { 1, 1, 1, 1 };
int value = 0, flag = 0, i, j;
for (j = 0; j < 4; j++)
{
value++;
for (i = 0; i < 3; i++)
{
if (checklist[j][i][0] != checklist[j][i][1])
{
value--;
returned[j] = 0;
break;
}
}
}
for (i = 0; i < 4; i++)
{
if (returned[i] && returned[(i + 1) % 4])
{
flag = 1;
}
}
return flag ? value : 0;
}
static int cube_check_bedges(CUBE* cube)
{
int checklist[][2][2] =
{
{
{ cube->u[1][1], cube->u[0][1] },
{ cube->b[1][1], cube->b[0][1] },
},
{
{ cube->d[1][1], cube->d[2][1] },
{ cube->b[1][1], cube->b[2][1] },
},
{
{ cube->l[1][1], cube->l[1][0] },
{ cube->b[1][1], cube->b[1][2] },
},
{
{ cube->r[1][1], cube->r[1][2] },
{ cube->b[1][1], cube->b[1][0] },
},
};
int value = 0, i, j;
for (j = 0; j < 4; j++)
{
value++;
for (i = 0; i < 2; i++)
{
if (checklist[j][i][0] != checklist[j][i][1])
{
value--;
break;
}
}
}
return value;
}
static int cube_check_state(CUBE* cube, int flag)
{
int (*pfn_check_tab[])(CUBE * cube) =
{
cube_check_fcross0,
cube_check_fcross1,
cube_check_fcorners,
cube_check_medges,
cube_check_bcross,
cube_check_bsurface,
cube_check_bcorners,
cube_check_bedges,
NULL,
};
int value = 0, cur, i;
for (i = 0; pfn_check_tab[i]; i++)
{
if (flag)
{
value += pfn_check_tab[i](cube);
cur += 4;
if (cur >= flag)
{
break;
}
}
else
{
cur = pfn_check_tab[i](cube);
value += cur;
if (cur != 4)
{
break;
}
}
}
return value;
}
typedef struct
{
int open ;
int close;
int size ;
CUBE* cubes;
} TABLE;
static int search_table_create(TABLE* table, int size)
{
table->size = size;
table->cubes = malloc(size * sizeof(CUBE));
return table->cubes ? 0 : -1;
}
static void search_table_destroy(TABLE* table)
{
if (table->cubes)
{
free(table->cubes);
table->cubes = NULL;
}
}
static int is_4same_ops(CUBE* cube)
{
int curop = cube->op;
int n = 0;
while (cube)
{
if (cube->op == curop)
{
if (++n == 4)
{
return 1;
}
cube = cube->parent;
}
else
{
break;
}
}
return 0;
}
static int cut_branch(int newval, int cutval)
{
return newval < cutval;
}
static CUBE* search(TABLE* table, CUBE* start, int state, char* oplist, int opnum, int cutval)
{
CUBE* curcube, *newcube;
int newstate, newvalue, i;
start->parent = NULL;
start->op = -1;
if (cube_check_state(start, 0) >= state)
{
return start;
}
// init search table
table->open = 0;
table->close = 0;
// put original cube into open table
table->cubes[table->open] = *start;
table->open++;
while (table->close < table->open)
{
// check memory usage
if (table->open + 6 >= table->size - 1)
{
printf("all table memory have been used !\n");
break;
}
// dequeue a cube from open table
curcube = &(table->cubes[table->close++]);
// extend cubes check state and put new cubes into open table
for (i = 0; i < opnum; i++)
{
newcube = &(table->cubes[table->open]);
memcpy(newcube, curcube, sizeof(CUBE));
cube_op(newcube, oplist[i]);
newcube->op = oplist[i];
newcube->parent = curcube;
newstate = cube_check_state(newcube, 0);
newvalue = cube_check_state(newcube, state);
if (newstate >= state) // found
{
return newcube;
}
if (is_4same_ops(newcube))
{
continue;
}
if (cut_branch(newvalue, cutval))
{
continue;
}
table->open++;
}
}
return NULL;
}
static void print_solve_oplist(CUBE* cube)
{
static char* optab[] =
{
"F", "B", "U", "D", "L", "R",
"F2", "B2", "U2", "D2", "L2", "R2",
"F'", "B'", "U'", "D'", "L'", "R'",
};
char* oplist[256];
int last = -1, times = 0, i = 0, n = 0;
while (cube)
{
if (cube->op >= 0)
{
if (last != cube->op)
{
if (last != -1)
{
oplist[i++] = optab[last + times * 6];
}
last = cube->op;
times = 0;
}
else
{
times++;
}
}
else
{
if (last != -1)
{
oplist[i++] = optab[last + times * 6];
}
}
cube = cube->parent;
}
printf("\noperation list:\n");
while (--i >= 0)
{
printf("%s%s%s", oplist[i], i == 0 ? "" : " -> ", ++n % 12 == 0 ? "\n" : "");
}
printf("\n");
}
static void cube_solve(CUBE* c)
{
TABLE t;
if (search_table_create(&t, 1024 * 1024 * 16) != 0)
{
printf("failed to create cube search table !\n");
return;
}
if (1)
{
static char oplisttab[][6] =
{
{ CUBE_OP_F, CUBE_OP_U, CUBE_OP_D, CUBE_OP_L, CUBE_OP_R },
{ CUBE_OP_U, CUBE_OP_D, CUBE_OP_L, CUBE_OP_R, CUBE_OP_B },
{ CUBE_OP_B, CUBE_OP_R, CUBE_OP_U },
};
static int stepparams[][4] =
{
{ 2, 0, 5, 0 }, //+ fcross0
{ 4, 0, 5, 2 }, //- fcross0
{ 8, 0, 5, 2 }, //+-fcross1
{ 9, 0, 5, 3 }, //+ fcorners
{ 10, 0, 5, 4 }, //..
{ 11, 0, 5, 5 }, //..
{ 12, 0, 5, 5 }, //- fcorners
{ 13, 1, 5, 6 }, //+ medges
{ 14, 1, 5, 6 }, //..
{ 15, 1, 5, 7 }, //..
{ 16, 1, 5, 8 }, //- medges
{ 18, 1, 5, 10}, //+ bcross
{ 20, 1, 5, 11}, //- bcross
{ 21, 1, 5, 11}, //+ bsurface
{ 24, 1, 5, 11}, //- bsurface
{ 26, 2, 3, 12}, //+ bcorners
{ 28, 2, 3, 12}, //- bcorners
{ 32, 2, 2, 12}, //+-bedges
{ 0, 0, 0, 0 },
};
CUBE* start = c;
CUBE* find = NULL;
int i;
for (i = 0; stepparams[i][0]; i++)
{
find = search(&t, start, stepparams[i][0], oplisttab[stepparams[i][1]], stepparams[i][2], stepparams[i][3]);
if (find)
{
if (find != start)
{
start = find;
*c = *find;
print_solve_oplist(find);
if (stepparams[i][0] != 32)
{
cube_render(c);
}
}
}
else
{
printf("can't solve !\n");
goto done;
}
}
printf("\ncube solved !\n");
}
done:
search_table_destroy(&t);
}
static void cube_input(CUBE* c)
{
char str[256];
printf("please input F surface of cube:\n");
scanf("%c %c %c %c %c %c %c %c %c",
&(c->f[0][0]), &(c->f[0][1]), &(c->f[0][2]),
&(c->f[1][0]), &(c->f[1][1]), &(c->f[1][2]),
&(c->f[2][0]), &(c->f[2][1]), &(c->f[2][2]));
gets(str);
printf("please input U surface of cube:\n");
scanf("%c %c %c %c %c %c %c %c %c",
&(c->u[0][0]), &(c->u[0][1]), &(c->u[0][2]),
&(c->u[1][0]), &(c->u[1][1]), &(c->u[1][2]),
&(c->u[2][0]), &(c->u[2][1]), &(c->u[2][2]));
gets(str);
printf("please input D surface of cube:\n");
scanf("%c %c %c %c %c %c %c %c %c",
&(c->d[0][0]), &(c->d[0][1]), &(c->d[0][2]),
&(c->d[1][0]), &(c->d[1][1]), &(c->d[1][2]),
&(c->d[2][0]), &(c->d[2][1]), &(c->d[2][2]));
gets(str);
printf("please input L surface of cube:\n");
scanf("%c %c %c %c %c %c %c %c %c",
&(c->l[0][0]), &(c->l[0][1]), &(c->l[0][2]),
&(c->l[1][0]), &(c->l[1][1]), &(c->l[1][2]),
&(c->l[2][0]), &(c->l[2][1]), &(c->l[2][2]));
gets(str);
printf("please input R surface of cube:\n");
scanf("%c %c %c %c %c %c %c %c %c",
&(c->r[0][0]), &(c->r[0][1]), &(c->r[0][2]),
&(c->r[1][0]), &(c->r[1][1]), &(c->r[1][2]),
&(c->r[2][0]), &(c->r[2][1]), &(c->r[2][2]));
gets(str);
printf("please input B surface of cube:\n");
scanf("%c %c %c %c %c %c %c %c %c",
&(c->b[0][0]), &(c->b[0][1]), &(c->b[0][2]),
&(c->b[1][0]), &(c->b[1][1]), &(c->b[1][2]),
&(c->b[2][0]), &(c->b[2][1]), &(c->b[2][2]));
gets(str);
}
static void show_help(void)
{
printf(
"\n"
"available commands:\n\n"
"f f2 f' b b2 b' u u2 u' d d2 d' l l2 l' r r2 r'\n"
"init rand input solve help exit\n\n"
"note: all command is case sensitive.\n"
);
}
int main(void)
{
char cmd[128];
char str[256];
CUBE c;
// init cube
cube_init(&c);
show_help();
while (1)
{
cube_render(&c);
printf("command: ");
scanf("%s", cmd);
if (strcmp(cmd, "f") == 0)
{
cube_f(&c);
}
else if (strcmp(cmd, "f2") == 0)
{
cube_f(&c);
cube_f(&c);
}
else if (strcmp(cmd, "f'") == 0)
{
cube_f(&c);
cube_f(&c);
cube_f(&c);
}
else if (strcmp(cmd, "b") == 0)
{
cube_b(&c);
}
else if (strcmp(cmd, "b2") == 0)
{
cube_b(&c);
cube_b(&c);
}
else if (strcmp(cmd, "b'") == 0)
{
cube_b(&c);
cube_b(&c);
cube_b(&c);
}
else if (strcmp(cmd, "u") == 0)
{
cube_u(&c);
}
else if (strcmp(cmd, "u2") == 0)
{
cube_u(&c);
cube_u(&c);
}
else if (strcmp(cmd, "u'") == 0)
{
cube_u(&c);
cube_u(&c);
cube_u(&c);
}
else if (strcmp(cmd, "d") == 0)
{
cube_d(&c);
}
else if (strcmp(cmd, "d2") == 0)
{
cube_d(&c);
cube_d(&c);
}
else if (strcmp(cmd, "d'") == 0)
{
cube_d(&c);
cube_d(&c);
cube_d(&c);
}
else if (strcmp(cmd, "l") == 0)
{
cube_l(&c);
}
else if (strcmp(cmd, "l2") == 0)
{
cube_l(&c);
cube_l(&c);
}
else if (strcmp(cmd, "l'") == 0)
{
cube_l(&c);
cube_l(&c);
cube_l(&c);
}
else if (strcmp(cmd, "r") == 0)
{
cube_r(&c);
}
else if (strcmp(cmd, "r2") == 0)
{
cube_r(&c);
cube_r(&c);
}
else if (strcmp(cmd, "r'") == 0)
{
cube_r(&c);
cube_r(&c);
cube_r(&c);
}
else if (strcmp(cmd, "init") == 0)
{
cube_init(&c);
}
else if (strcmp(cmd, "rand") == 0)
{
gets(str);
cube_rand(&c, atoi(str) == 0 ? 100 : atoi(str));
}
else if (strcmp(cmd, "input") == 0)
{
cube_input(&c);
}
else if (strcmp(cmd, "solve") == 0)
{
cube_solve(&c);
}
else if (strcmp(cmd, "help") == 0)
{
show_help();
}
else if (strcmp(cmd, "exit") == 0)
{
break;
}
else
{
printf("unsupported command !\n");
}
printf("\n");
}
return 0;
}
[此贴子已经被作者于2019-4-28 23:06编辑过]
我就是真命天子，顺我者生，逆我者死！
，希望作者能帮我解答