手搓哈希表、列表、队列，只为了用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] ↓

思路

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/196535.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

掌握PyQt6/Pyside6如何用QTreeView QFileSystemModel 展示指定目录结构

掌握PyQt6/Pyside6如何用QTreeView QFileSystemModel 展示指定目录结构

文章目录 📖 介绍 📖🏡 环境 🏡📄 源码📖 介绍 📖 有时候我们需要给用户展示一个指定目录下的所有文件树结构，这里使用 PyQt6/Pyside6的QTreeView就可以轻松实现，本文将与大家分享实现源码 🏡 环境 🏡 本文代码运行的环境如下 Windows11Python3.11.5PySide…
阅读更多...
【C++】多线程的学习笔记（3）——白话文版（bushi

【C++】多线程的学习笔记（3）——白话文版（bushi

目录 前一篇内容&#xff08;mutex锁&#xff09; 前言 Condition Variable的简介 Condition Variable的使用方法 wait方法 wait for函数与wait until函数 notify函数 notify_one notify_all 注意 前一篇内容&#xff08;mutex锁&#xff09; 【C】多线程的学习笔记&…
阅读更多...
保姆级前端翻牌效果(CSS)

保姆级前端翻牌效果(CSS)

效果 翻牌效果 hover 时候 代码直接上 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document<…
阅读更多...
android适配鸿蒙系统开发

android适配鸿蒙系统开发

将一个Android应用迁移到鸿蒙系统需要进行细致的工作&#xff0c;因为两者之间存在一些根本性的差异&#xff0c;涉及到代码、架构、界面等多个方面的修改和适配。以下是迁移工作可能涉及的一些主要方面&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专…
阅读更多...
在QGIS中加载显示3DTiles数据

在QGIS中加载显示3DTiles数据

“我们最近有机会在QGIS 3.34中实现一个非常令人兴奋的功能–能够以“Cesium 3D Tiles”格式加载和查看3D内容&#xff01;” ——QGIS官方的 宣传介绍。 体验一下&#xff0c;感觉就是如芒刺背、如坐针毡、如鲠在喉。 除非我电脑硬件有问题&#xff0c;要么QGIS的3Dtiles是真…
阅读更多...
企业邮箱认证指南：安全与高效的邮箱认证方法

企业邮箱认证指南：安全与高效的邮箱认证方法

企业邮箱是专门为企业提供的电子邮件服务&#xff0c;安全性和专业性更高。在开始使用企业邮箱之前&#xff0c;很多人会有一些问题&#xff0c;比如企业邮箱需要认证吗、如何开通企业邮箱&#xff0c;以及哪款企业邮箱好。 1、企业邮箱在使用前需要认证吗&#xff1f; 答案是肯…
阅读更多...
【机器学习8】采样

【机器学习8】采样

1 均匀分布随机数 均匀分布是指整个样本空间中的每一个样本点对应的概率&#xff08;密度&#xff09; 都是相等的。 根据样本空间是否连续&#xff0c; 又分为离散均匀分布和连续均匀分布。编程实现均匀分布随机数生成器一般可采用线性同余法&#xff08;Linear Congruential…
阅读更多...
二维码智慧门牌管理系统升级解决方案：门牌聚合，让管理更便捷！

二维码智慧门牌管理系统升级解决方案：门牌聚合，让管理更便捷！

文章目录 前言一、传统门牌管理系统的瓶颈二、地图门牌聚合展示的优势三、地图门牌聚合展示的实现方法四、智慧门牌管理系统的未来发展 前言 随着城市的发展和建设&#xff0c;对于地址信息的管理变得越来越重要。而智慧门牌管理系统作为管理地址信息的重要工具&#xff0c;其…
阅读更多...
原来机械硬盘比内存慢10万倍

原来机械硬盘比内存慢10万倍

我们都知道机械硬盘的速度很慢&#xff0c;内存的速度很快&#xff0c;那么不同存储器之间的差距到底有多大呢&#xff1f; 我们先来看一幅图&#xff1a; CPU访问寄存器的时间是0.3纳秒&#xff0c;访问L1高速缓存的时间是1纳秒&#xff0c;访问L2高速缓存的时间是4纳秒… 秒…
阅读更多...
设计模式-状态模式-笔记

设计模式-状态模式-笔记

状态模式State 在组件构建过程中&#xff0c;某些对象的状态经常面临变化&#xff0c;如何对这些变化进行有效的管理&#xff1f;同时又维持高层模块的稳定&#xff1f;“状态变化”模式为这一问题提供了一种解决方案。 经典模式&#xff1a;State、Memento 动机&#xff08…
阅读更多...
基于RFbeam的V-LD1-60GHz毫米波雷达传感器数据获取（通过UART串口来控制模块）

基于RFbeam的V-LD1-60GHz毫米波雷达传感器数据获取（通过UART串口来控制模块）

基于RFbeam的V-LD1-60GHz毫米波雷达传感器数据获取&#xff08;通过UART串口来控制模块&#xff09; 工程&#xff1a; Keil工程资源 文章目录 V-LD1命令发送消息回复通信示例雷达数据获取宏定义通信代码运行效果附录&#xff1a;压缩字符串、大小端格式转换压缩字符串浮点数压…
阅读更多...
Selenium自动化测试框架

Selenium自动化测试框架

一.Selenium概述 1.1 什么是框架? 框架&#xff08;framework&#xff09;是一个框子——指其约束性&#xff0c;也是一个架子——指其支撑性。是一个基本概念上的 结构用于去解决或者处理复杂的问题。 框架是整个或部分系统的可重用设计&#xff0c;表现为一组抽象构件及…
阅读更多...
ARDUINO UNO 12颗LED超酷流水灯效果

ARDUINO UNO 12颗LED超酷流水灯效果

效果代码&#xff1a; #define t 30 #define t1 20 #define t2 100 #define t3 50 void setup() { // set up pins 2 to 13 as outputs for (int i 2; i < 13; i) { pinMode(i, OUTPUT); } } /Effect 1 void loop() { effect_1(); effect_1(); effect_…
阅读更多...
目标检测—YOLO系列(二 ) 全面解读复现YOLOv1 PyTorch

目标检测—YOLO系列(二 ) 全面解读复现YOLOv1 PyTorch

精读论文 前言 从这篇开始&#xff0c;我们将进入YOLO的学习。YOLO是目前比较流行的目标检测算法&#xff0c;速度快且结构简单&#xff0c;其他的目标检测算法如RCNN系列&#xff0c;以后有时间的话再介绍。 本文主要介绍的是YOLOV1&#xff0c;这是由以Joseph Redmon为首的…
阅读更多...
Kafka 集群实现数据同步

Kafka 集群实现数据同步

Kafka 介绍 Kafka 是一个高吞吐的分布式消息系统&#xff0c;不但像传统消息队列&#xff08;RaabitMQ、RocketMQ等&#xff09;那样能够【异步处理、流量消峰、服务解耦】 还能够把消息持久化到磁盘上&#xff0c;用于批量消费。除此之外由于 Kafka 被设计成分布式系统&…
阅读更多...
spring学习笔记-IOC，AOP，事务管理

spring学习笔记-IOC，AOP，事务管理

目录 概述 什么是spring 侵入式的概念 spring的核心 spring的优势 注意 IOC控制反转 概述 核心 容器 DI&#xff0c;dependency injection依赖注入 概念 注入方式 循环依赖 spring如何解决循环依赖 spring生成Bean的方式 Bean属性注入&#xff08;Bean属性赋值…
阅读更多...
Confluence 快速安装教程

Confluence 快速安装教程

安装jdk yum install -y java-1.8.0-openjdk.x86_64 java -version 安装MySQL mkdir -p /data/mysql/data chmod 777 /data/mysql/datadocker rm -f mysql docker run -d --name mysql \-p 3306:3306 \-e MYSQL_ROOT_PASSWORDfingard1 \-v /data/mysql/data:/var/lib/mysql …
阅读更多...
Spring学习③__Bean管理

Spring学习③__Bean管理

目录 IOC接口ApplicationContext 详解IOC操作Bean管理基于xml方式基于xml方式创建对象基于xml方式注入属性使用set方法进行注入通过有参数的构造进行注入p 名称空间注入&#xff08;了解&#xff09; 基于xml方式注入其他类型属性xml 注入数组类型属性 IOC接口 IOC思想基于IOC…
阅读更多...
CSS特效013：背景色彩不停流动效果

CSS特效013：背景色彩不停流动效果

CSS常用示例100专栏目录 本专栏记录的是经常使用的CSS示例与技巧&#xff0c;主要包含CSS布局&#xff0c;CSS特效&#xff0c;CSS花边信息三部分内容。其中CSS布局主要是列出一些常用的CSS布局信息点&#xff0c;CSS特效主要是一些动画示例&#xff0c;CSS花边是描述了一些CSS…
阅读更多...
CTF-PWN-tips

CTF-PWN-tips

文章目录 overflowscanfgetreadstrcpystrcat Find string in gdbgdbgdb peda Binary ServiceFind specific function offset in libc手工自动 Find /bin/sh or sh in library手动自动 Leak stack addressFork problem in gdbSecret of a mysterious section - .tlsPredictable …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023