网站建站软件,织梦手机网站免费模板,中国免费广告网,ps设计网页效果图背景
多年前曾经写过C语言求解华容道#xff0c;当时没有用到哈希表#xff0c;导致整个查重搜索数组过大#xff0c;每次求解都得花上数分钟的时间#xff0c;如今时过境迁#xff0c;对数据结构和算法有了更深的理解#xff0c;所以得把这一块补上了。(其实就是最近想…背景
多年前曾经写过C语言求解华容道当时没有用到哈希表导致整个查重搜索数组过大每次求解都得花上数分钟的时间如今时过境迁对数据结构和算法有了更深的理解所以得把这一块补上了。(其实就是最近想换工作发现都喜欢算法大佬所以写一个来敲一敲面试官的脑壳)
游戏
华容道挑战 7724游戏
方案 把曹操格子用1表示横将用2表示竖将用3表示小兵用4表示空地用0表示上图可以转化了代号
2244
3110
3110
3433
3433
把上术内容保存到文本文件problem.txt当中
编写源文件main.c内容为
/*依赖库导入 start*/
#includestdio.h /* 标准输入输出库 */
#includestring.h /* 字符串处理库 */
#includemalloc.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(i0; i5; i) {scanf(%s,arr[i]);printf(%s\n,arr[i]);}printf(\n);
}/* 获取字符数组哈希码 */
int hashCode(char **arr,char value[]) {int res0;int i,j,k0;for(i0; i5; i) {for(j0; j4; j) {value[k]arr[i][j];k;resres*PRIMERarr[i][j]-0;res%MOD;}}return res;
}/* 往哈希表中添加对象 */
int addObjectToHashSet(char **arr,HashSet *hashSet) {char value[21] {\0};int codehashCode(arr,value);LinkList *linkListhashSet-linkList[code];while(linkList!NULL) {if(strcmp(linkList-str,value)0) {return 0;} else {linkListlinkList-next;}}LinkList *listHead(LinkList*)malloc(sizeof(LinkList));listHead-str(char*)malloc(sizeof(char)*21);strcpy(listHead-str,value);listHead-nexthashSet-linkList[code];hashSet-linkList[code]listHead;return 1;
}/* 释放哈希表 */
void freeHashSet(HashSet *hashSet) {int i;for(i0; iMOD; i) {while(hashSet-linkList[i]!NULL) {LinkList *linkListhashSet-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(i0; i5; i) {node-arr[i](char*)malloc(sizeof(char)*5);strcpy(node-arr[i],arr[i]);}if(x-1||y-1||direction-1) {node-operationNULL;} else {node-operation(Operation*)malloc(sizeof(Operation));node-operation-xx;node-operation-yy;node-operation-directiondirection;}node-previousNULL;node-nextNULL;if(queue-headNULL) {queue-headnode;queue-tailnode;queue-count0;} else {queue-tail-nextnode;node-previousqueue-head;queue-tailnode;}queue-count;
}/* 出队 */
void deQueue(Queue *queue) {queue-headqueue-head-next;queue-count--;
}/* 释放队列 */
void freeQueue(Queue *queue) {while(queue-head!NULL) {Node* nodequeue-head;queue-headqueue-head-next;if(node-operation!NULL) {free(node-operation);}if(node-arr!NULL) {int i;for(i0; i5; i) {free(node-arr[i]);}free(node-arr);}}free(queue);
}/* 生成格子链表 */
Block* getBlocks(char **arr) {int i,j,u,v;Block* blocksNULL;char temp[5][4] {0};for(i0; i5; i) {strcpy(temp[i],arr[i]);}for(i0; i5; i) {for(j0; j4; j) {if(temp[i][j]SPACE) {continue;}Block *block(Block*)malloc(sizeof(Block));block-nextblocks;blocksblock;block-typetemp[i][j];block-xi;block-yj;switch(temp[i][j]) {case BIG:block-w2;block-h2;break;case HORIZONTAL:block-w2;block-h1;break;case VERTICAL:block-w1;block-h2;break;case SMALL:block-w1;block-h1;break;}for(ui; uiblock-h; u) {for(vj; vjblock-w; v) {temp[u][v]SPACE;}}}}return blocks;
}/* 释放格子链表 */
void freeBlocks(Block *blocks) {while(blocks-next!NULL) {Block *blockblocks;blocksblocks-next;free(block);}
}/* 创建字符数组 */
char** createArray() {int i,j;char** res(char**)malloc(sizeof(char*)*5);for(i0; i5; i) {res[i](char*)malloc(sizeof(char)*5);for(j0; j4; j) {res[i][j]0;}res[i][4]\0;}return res;
}/* 释放字符数组 */
void freeArray(char **arr) {int i;for(i0; i5; i) {free(arr[i]);}free(arr);
}/* 方块转字符数组 */
void blocksToArray(Block *blocks,char **arr) {int i,j;while(blocks!NULL) {Block *blockblocks;blocksblocks-next;for(iblock-x; iblock-xblock-h; i) {for(jblock-y; jblock-yblock-w; j) {arr[i][j]block-type;}}}
}/* 打印所求结果 */
void displaySolution(Node *node) {if(node-operationNULL) {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(i0; i5; i) {array[i](char*)malloc(sizeof(char)*5);array[i][4]\0;}if(argc2) {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(i0; iMOD; i) {hashSet.linkList[i]NULL;}Queue queue;queue.headNULL;queue.tailNULL;Node *resultNULL;addObjectToHashSet(array,hashSet);enQueue(array,-1,-1,-1,queue);free(array);while(queue.head!NULL) {Node *nodequeue.head;if(node-arr[3][1]BIG node-arr[4][2]BIG) {resultnode;break;}Block *blocksgetBlocks(node-arr);Block *blocksHeadblocks;while(blocksHead!NULL) {Block *blockblocksHead;blocksHeadblocksHead-next;char **arrNULL;switch(block-type) {case BIG:if(block-x0 node-arr[block-x-1][block-y]SPACE node-arr[block-x-1][block-y1]SPACE) {arrcreateArray();block-x--;blocksToArray(blocks,arr);block-x;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,UP,queue);}}if(block-xblock-h5 node-arr[block-xblock-h][block-y]SPACE node-arr[block-xblock-h][block-y1]SPACE) {arrcreateArray();block-x;blocksToArray(blocks,arr);block-x--;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,DOWN,queue);}}if(block-y0 node-arr[block-x][block-y-1]SPACE node-arr[block-x1][block-y-1]SPACE) {arrcreateArray();block-y--;blocksToArray(blocks,arr);block-y;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,LEFT,queue);}}if(block-yblock-w4 node-arr[block-x][block-yblock-w]SPACE node-arr[block-x1][block-yblock-w]SPACE) {arrcreateArray();block-y;blocksToArray(blocks,arr);block-y--;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,RIGHT,queue);}}break;case HORIZONTAL:if(block-x0 node-arr[block-x-1][block-y]SPACE node-arr[block-x-1][block-y1]SPACE) {arrcreateArray();block-x--;blocksToArray(blocks,arr);block-x;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,UP,queue);}}if(block-xblock-h5 node-arr[block-xblock-h][block-y]SPACE node-arr[block-xblock-h][block-y1]SPACE) {arrcreateArray();block-x;blocksToArray(blocks,arr);block-x--;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,DOWN,queue);}}if(block-y0 node-arr[block-x][block-y-1]SPACE) {arrcreateArray();block-y--;blocksToArray(blocks,arr);block-y;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,LEFT,queue);}}if(block-yblock-w4 node-arr[block-x][block-yblock-w]SPACE) {arrcreateArray();block-y;blocksToArray(blocks,arr);block-y--;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,RIGHT,queue);}}break;case VERTICAL:if(block-x0 node-arr[block-x-1][block-y]SPACE) {arrcreateArray();block-x--;blocksToArray(blocks,arr);block-x;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,UP,queue);}}if(block-xblock-h5 node-arr[block-xblock-h][block-y]SPACE) {arrcreateArray();block-x;blocksToArray(blocks,arr);block-x--;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,DOWN,queue);}}if(block-y0 node-arr[block-x][block-y-1]SPACE node-arr[block-x1][block-y-1]SPACE) {arrcreateArray();block-y--;blocksToArray(blocks,arr);block-y;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,LEFT,queue);}}if(block-yblock-w4 node-arr[block-x][block-yblock-w]SPACE node-arr[block-x1][block-yblock-w]SPACE) {arrcreateArray();block-y;blocksToArray(blocks,arr);block-y--;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,RIGHT,queue);}}break;case SMALL:if(block-x0 node-arr[block-x-1][block-y]SPACE) {arrcreateArray();block-x--;blocksToArray(blocks,arr);block-x;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,UP,queue);}}if(block-xblock-h5 node-arr[block-xblock-h][block-y]SPACE) {arrcreateArray();block-x;blocksToArray(blocks,arr);block-x--;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,DOWN,queue);}}if(block-y0 node-arr[block-x][block-y-1]SPACE) {arrcreateArray();block-y--;blocksToArray(blocks,arr);block-y;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,LEFT,queue);}}if(block-yblock-w4 node-arr[block-x][block-yblock-w]SPACE) {arrcreateArray();block-y;blocksToArray(blocks,arr);block-y--;if(addObjectToHashSet(arr,hashSet)) {enQueue(arr,block-x,block-y,RIGHT,queue);}}break;}}while(blocks!NULL) {blocksHeadblocks;blocksblocks-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] ↓思路
之前已经有博文进行了详细介绍此处不再赘述。
