手搓哈希表、列表、队列，只为了用C语言快速求解华容道游戏，我不是大佬，只是一个游戏算法爱好者
背景
多年前曾经写过C语言求解华容道，当时没有用到哈希表，导致整个查重搜索数组过大，每次求解都得花上数分钟的时间，如今时过境迁，对数据结构和算法有了更深的理解，所以得把这一块补上了。(其实就是最近想换工作，发现都喜欢算法大佬，所以写一个来敲一敲面试官的脑壳)
游戏
华容道挑战 7724游戏
方案
把曹操格子用1表示，横将用2表示，竖将用3表示，小兵用4表示，空地用0表示，上图可以转化了代号
2244
3110
3110
3433
3433把上术内容保存到文本文件problem.txt当中
编写源文件main.c，内容为
/*==============依赖库导入 start================*/
#include<stdio.h> /* 标准输入输出库 */
#include<string.h> /* 字符串处理库 */
#include<malloc.h> /* 动态内存管理库 */
/*==============依赖库导入 end==================*/
/*================宏定义 start==================*/
/* 格子宏 */
#define SPACE '0' /* 空格 */
#define BIG '1' /* 大格 */
#define HORIZONTAL '2' /* 横格 */
#define VERTICAL '3' /* 竖格 */
#define SMALL '4' /* 小格 */
/* 方向宏 */
#define UP 1 /* 上 */
#define DOWN 2 /* 下 */
#define LEFT 3 /* 左 */
#define RIGHT 4 /* 右 */
/* 哈希宏 */
#define PRIMER 31 /* 素数系数 */
#define MOD 10007 /* 素数哈希 */
/*================宏定义 end====================*/
/*===============数据结构 start=================*/
typedef struct LinkList { /* 链表 */
char *str; /* 字符串 */
struct LinkList *next; /* 下一个节点指针 */
} LinkList;
typedef struct HashSet { /* 哈希集合 */
LinkList *linkList[MOD]; /* 链表数组 */
} HashSet;
typedef struct Block { /* 方块 */
char type; /* 类型 */
int x; /* 左上角横坐标 */
int y; /* 左上角纵坐标 */
int w,h; /* 格子宽高 */
struct Block *next; /* 下一个节点 */
} Block;
typedef struct Operation { /* 操作 */
int x,y; /* 格子位置 */
int direction; /* 移动类型 */
} Operation;
typedef struct Node { /* 节点 */
char **arr; /* 字符数组 */
Operation *operation; /* 上一步操作 */
struct Node *previous; /* 上一个节点 */
struct Node *next; /* 下一个节点 */
} Node;
typedef struct Queue { /* 队列 */
Node *head; /* 队头 */
Node *tail; /* 队尾 */
int count; /* 数量 */
} Queue;
/*===============数据结构 end===================*/
/* 从文件读取题目 */
void readProblemFile(char **arr,char *filepath) {
freopen(filepath,"r",stdin);
int i,j;
for(i=0; i<5; i++) {
scanf("%s",arr[i]);
printf("%s\n",arr[i]);
}
printf("\n");
}
/* 获取字符数组哈希码 */
int hashCode(char **arr,char value[]) {
int res=0;
int i,j,k=0;
for(i=0; i<5; i++) {
for(j=0; j<4; j++) {
value[k]=arr[i][j];
k++;
res=res*PRIMER+arr[i][j]-'0';
res%=MOD;
}
}
return res;
}
/* 往哈希表中添加对象 */
int addObjectToHashSet(char **arr,HashSet *hashSet) {
char value[21]= {'\0'};
int code=hashCode(arr,value);
LinkList *linkList=hashSet->linkList[code];
while(linkList!=NULL) {
if(strcmp(linkList->str,value)==0) {
return 0;
} else {
linkList=linkList->next;
}
}
LinkList *listHead=(LinkList*)malloc(sizeof(LinkList));
listHead->str=(char*)malloc(sizeof(char)*21);
strcpy(listHead->str,value);
listHead->next=hashSet->linkList[code];
hashSet->linkList[code]=listHead;
return 1;
}
/* 释放哈希表 */
void freeHashSet(HashSet *hashSet) {
int i;
for(i=0; i<MOD; i++) {
while(hashSet->linkList[i]!=NULL) {
LinkList *linkList=hashSet->linkList[i];
hashSet->linkList[i]=hashSet->linkList[i]->next;
free(linkList);
}
}
free(hashSet);
}
/* 入队 */
void enQueue(char **arr,int x,int y,int direction,Queue *queue) {
int i;
Node *node=(Node*)malloc(sizeof(Node));
node->arr=(char**)malloc(sizeof(char*)*5);
for(i=0; i<5; i++) {
node->arr[i]=(char*)malloc(sizeof(char)*5);
strcpy(node->arr[i],arr[i]);
}
if(x==-1||y==-1||direction==-1) {
node->operation=NULL;
} else {
node->operation=(Operation*)malloc(sizeof(Operation));
node->operation->x=x;
node->operation->y=y;
node->operation->direction=direction;
}
node->previous=NULL;
node->next=NULL;
if(queue->head==NULL) {
queue->head=node;
queue->tail=node;
queue->count=0;
} else {
queue->tail->next=node;
node->previous=queue->head;
queue->tail=node;
}
queue->count++;
}
/* 出队 */
void deQueue(Queue *queue) {
queue->head=queue->head->next;
queue->count--;
}
/* 释放队列 */
void freeQueue(Queue *queue) {
while(queue->head!=NULL) {
Node* node=queue->head;
queue->head=queue->head->next;
if(node->operation!=NULL) {
free(node->operation);
}
if(node->arr!=NULL) {
int i;
for(i=0; i<5; i++) {
free(node->arr[i]);
}
free(node->arr);
}
}
free(queue);
}
/* 生成格子链表 */
Block* getBlocks(char **arr) {
int i,j,u,v;
Block* blocks=NULL;
char temp[5][4]= {0};
for(i=0; i<5; i++) {
strcpy(temp[i],arr[i]);
}
for(i=0; i<5; i++) {
for(j=0; j<4; j++) {
if(temp[i][j]==SPACE) {
continue;
}
Block *block=(Block*)malloc(sizeof(Block));
block->next=blocks;
blocks=block;
block->type=temp[i][j];
block->x=i;
block->y=j;
switch(temp[i][j]) {
case BIG:
block->w=2;
block->h=2;
break;
case HORIZONTAL:
block->w=2;
block->h=1;
break;
case VERTICAL:
block->w=1;
block->h=2;
break;
case SMALL:
block->w=1;
block->h=1;
break;
}
for(u=i; u<i+block->h; u++) {
for(v=j; v<j+block->w; v++) {
temp[u][v]=SPACE;
}
}
}
}
return blocks;
}
/* 释放格子链表 */
void freeBlocks(Block *blocks) {
while(blocks->next!=NULL) {
Block *block=blocks;
blocks=blocks->next;
free(block);
}
}
/* 创建字符数组 */
char** createArray() {
int i,j;
char** res=(char**)malloc(sizeof(char*)*5);
for(i=0; i<5; i++) {
res[i]=(char*)malloc(sizeof(char)*5);
for(j=0; j<4; j++) {
res[i][j]='0';
}
res[i][4]='\0';
}
return res;
}
/* 释放字符数组 */
void freeArray(char **arr) {
int i;
for(i=0; i<5; i++) {
free(arr[i]);
}
free(arr);
}
/* 方块转字符数组 */
void blocksToArray(Block *blocks,char **arr) {
int i,j;
while(blocks!=NULL) {
Block *block=blocks;
blocks=blocks->next;
for(i=block->x; i<block->x+block->h; i++) {
for(j=block->y; j<block->y+block->w; j++) {
arr[i][j]=block->type;
}
}
}
}
/* 打印所求结果 */
void displaySolution(Node *node) {
if(node->operation==NULL) {
return;
} else {
displaySolution(node->previous);
int i;
char directionName[][10]= {"","↑","↓","←","→"};
printf("[%d,%d] %s\n",node->operation->x,node->operation->y,directionName[node->operation->direction]);
}
}
/* 主函数 */
int main(int argc,char *argv[]) {
char **array=(char**)malloc(sizeof(char*)*5);
int i,j;
for(i=0; i<5; i++) {
array[i]=(char*)malloc(sizeof(char)*5);
array[i][4]='\0';
}
if(argc==2) {
readProblemFile(array,argv[1]);
} else {
strcpy(array[0],"3113\0");
strcpy(array[1],"3113\0");
strcpy(array[2],"3223\0");
strcpy(array[3],"3443\0");
strcpy(array[4],"4004\0");
}
HashSet hashSet;
for(i=0; i<MOD; i++) {
hashSet.linkList[i]=NULL;
}
Queue queue;
queue.head=NULL;
queue.tail=NULL;
Node *result=NULL;
addObjectToHashSet(array,&hashSet);
enQueue(array,-1,-1,-1,&queue);
free(array);
while(queue.head!=NULL) {
Node *node=queue.head;
if(node->arr[3][1]==BIG && node->arr[4][2]==BIG) {
result=node;
break;
}
Block *blocks=getBlocks(node->arr);
Block *blocksHead=blocks;
while(blocksHead!=NULL) {
Block *block=blocksHead;
blocksHead=blocksHead->next;
char **arr=NULL;
switch(block->type) {
case BIG:
if(block->x>0 && node->arr[block->x-1][block->y]==SPACE && node->arr[block->x-1][block->y+1]==SPACE) {
arr=createArray();
block->x--;
blocksToArray(blocks,arr);
block->x++;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,UP,&queue);
}
}
if(block->x+block->h<5 && node->arr[block->x+block->h][block->y]==SPACE && node->arr[block->x+block->h][block->y+1]==SPACE) {
arr=createArray();
block->x++;
blocksToArray(blocks,arr);
block->x--;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,DOWN,&queue);
}
}
if(block->y>0 && node->arr[block->x][block->y-1]==SPACE && node->arr[block->x+1][block->y-1]==SPACE) {
arr=createArray();
block->y--;
blocksToArray(blocks,arr);
block->y++;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,LEFT,&queue);
}
}
if(block->y+block->w<4 && node->arr[block->x][block->y+block->w]==SPACE && node->arr[block->x+1][block->y+block->w]==SPACE) {
arr=createArray();
block->y++;
blocksToArray(blocks,arr);
block->y--;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,RIGHT,&queue);
}
}
break;
case HORIZONTAL:
if(block->x>0 && node->arr[block->x-1][block->y]==SPACE && node->arr[block->x-1][block->y+1]==SPACE) {
arr=createArray();
block->x--;
blocksToArray(blocks,arr);
block->x++;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,UP,&queue);
}
}
if(block->x+block->h<5 && node->arr[block->x+block->h][block->y]==SPACE && node->arr[block->x+block->h][block->y+1]==SPACE) {
arr=createArray();
block->x++;
blocksToArray(blocks,arr);
block->x--;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,DOWN,&queue);
}
}
if(block->y>0 && node->arr[block->x][block->y-1]==SPACE) {
arr=createArray();
block->y--;
blocksToArray(blocks,arr);
block->y++;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,LEFT,&queue);
}
}
if(block->y+block->w<4 && node->arr[block->x][block->y+block->w]==SPACE) {
arr=createArray();
block->y++;
blocksToArray(blocks,arr);
block->y--;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,RIGHT,&queue);
}
}
break;
case VERTICAL:
if(block->x>0 && node->arr[block->x-1][block->y]==SPACE) {
arr=createArray();
block->x--;
blocksToArray(blocks,arr);
block->x++;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,UP,&queue);
}
}
if(block->x+block->h<5 && node->arr[block->x+block->h][block->y]==SPACE) {
arr=createArray();
block->x++;
blocksToArray(blocks,arr);
block->x--;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,DOWN,&queue);
}
}
if(block->y>0 && node->arr[block->x][block->y-1]==SPACE && node->arr[block->x+1][block->y-1]==SPACE) {
arr=createArray();
block->y--;
blocksToArray(blocks,arr);
block->y++;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,LEFT,&queue);
}
}
if(block->y+block->w<4 && node->arr[block->x][block->y+block->w]==SPACE && node->arr[block->x+1][block->y+block->w]==SPACE) {
arr=createArray();
block->y++;
blocksToArray(blocks,arr);
block->y--;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,RIGHT,&queue);
}
}
break;
case SMALL:
if(block->x>0 && node->arr[block->x-1][block->y]==SPACE) {
arr=createArray();
block->x--;
blocksToArray(blocks,arr);
block->x++;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,UP,&queue);
}
}
if(block->x+block->h<5 && node->arr[block->x+block->h][block->y]==SPACE) {
arr=createArray();
block->x++;
blocksToArray(blocks,arr);
block->x--;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,DOWN,&queue);
}
}
if(block->y>0 && node->arr[block->x][block->y-1]==SPACE) {
arr=createArray();
block->y--;
blocksToArray(blocks,arr);
block->y++;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,LEFT,&queue);
}
}
if(block->y+block->w<4 && node->arr[block->x][block->y+block->w]==SPACE) {
arr=createArray();
block->y++;
blocksToArray(blocks,arr);
block->y--;
if(addObjectToHashSet(arr,&hashSet)) {
enQueue(arr,block->x,block->y,RIGHT,&queue);
}
}
break;
}
}
while(blocks!=NULL) {
blocksHead=blocks;
blocks=blocks->next;
free(blocksHead);
}
deQueue(&queue);
}
if(result!=NULL) {
printf("求解完成\n");
displaySolution(result);
} else {
printf("此题无解\n");
}
freeHashSet(&hashSet);
freeQueue(&queue);
return 0;
}编译源文件main.c得到可执行程序main.exe，把main.exe和problem.txt放在同一个文件夹下。
使用cmd打开此目录，执行命令
main.exe problem.txt > 1.txt稍后便可在目录下生成1.txt文件，里边保存的就是游戏的通关参考答案。
2244
3110
3110
3433
3433
求解完成
[3,3] ↑
[2,3] ↑
[3,2] →
[4,1] →
[3,1] ↓
[1,1] ↓
[0,2] ↓
[1,2] ←
[0,3] ←
[1,3] ↑
[3,3] ↑
[4,2] →
[0,2] ↓
[0,0] →
[1,0] ↑
[3,0] ↑
[4,1] ←
[2,1] ↓
思路
之前已经有博文进行了详细介绍，此处不再赘述。