手搓哈希表、列表、队列，只为了用C语言快速求解华容道游戏，我不是大佬，只是一个游戏算法爱好者

背景

多年前曾经写过C语言求解华容道，当时没有用到哈希表，导致整个查重搜索数组过大，每次求解都得花上数分钟的时间，如今时过境迁，对数据结构和算法有了更深的理解，所以得把这一块补上了。(其实就是最近想换工作，发现都喜欢算法大佬，所以写一个来敲一敲面试官的脑壳)

游戏

华容道挑战 7724游戏

方案

把曹操格子用1表示，横将用2表示，竖将用3表示，小兵用4表示，空地用0表示，上图可以转化了代号

22443110311034333433

把上术内容保存到文本文件problem.txt当中

编写源文件main.c，内容为

/*==============依赖库导入 start================*/#include/* 标准输入输出库 */#include/* 字符串处理库 */#include/* 动态内存管理库 *//*==============依赖库导入 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; jlinkList[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; ilinkList[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; iarr[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; iarr[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; jnext=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; uh; u++) {for(v=j; vw; 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; inext;for(i=block->x; ix+block->h; i++) {for(j=block->y; jy+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; iarr[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->harr[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->warr[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->harr[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->warr[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->harr[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->warr[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->harr[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->warr[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文件，里边保存的就是游戏的通关参考答案。

22443110311034333433求解完成[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] ↓

思路

之前已经有博文进行了详细介绍，此处不再赘述。