小项目:迷宫二

2023-12-18 00:12:58

引言

这个迷宫项目是今天参加学校的一个比赛出的题目,从早上九点基本搞到了四五点才完成,其实写出来发现基本思路其实挺简单的,就是想不好想,真的要各种的尝试,也训练反应和一个执行力,不过也算挺好的,现在给出题目。

一、题目描述

题目描述:
勇敢的盖伦前往诺克萨斯的地牢去解救美丽的光辉女神拉克丝,但是诺克萨斯的地牢机关重重、危机四
伏,请你帮助盖伦解救拉克丝。
诺克萨斯的地牢是一个14×14 的矩阵,该矩阵由如下几种元素组成:道路、墙壁、炸弹、传送门、怪物
组成,如下图所示:

在这里插入图片描述

解题规则
(1)盖伦拥有初始值为100的生命值,初始位置在矩阵中第2行第1列;拉克丝被关押的位置在矩阵中
第12行第13列;盖伦到达拉克丝所在的格子,则视为解救成功;
(2)白色格子为道路,盖伦可以到达;盖伦只能朝正北、正南、正东、正西这四个方向移动,每次只
能移动一格;
(3)褐色格子为墙壁,盖伦不可到达;
(4)炸弹放置在道路上,当盖伦到达该格子时则引发爆炸,盖伦自身扣除10生命值,同时炸弹将周边
(8个格子)存在的墙壁炸开变为道路,如周边存在怪物也一同炸消失;
(5)地牢中有10只小怪和3只大龙放置在道路上;当盖伦到达小怪格子,盖伦自身扣除5生命值,同时
该小怪消失;当盖伦到达大龙格子,盖伦自身扣除20生命值,同时该大龙消失;
(6)地牢中有3组传送门放置在道路上,其中A-B一组、C-D一组、E-F一组;当盖伦从别的非传送门格
子到达传送门A格子时,立即位移到传送门B格子,反之亦然;C-D传送门,E-F传送门同理。
问题求解
(1)盖伦是否能在存活的情况下,解救拉克丝?
(2)哪种解救方案(盖伦移动的路径)可以让盖伦扣除最少的生命值?
(3)自行设计一个 20×20 的地牢,其中至少包含12个炸弹、15只小怪、6只大龙、6组传送门;墙壁
的个数至少是所有格子的一半;盖伦初始位置在第1行第1列,拉克丝被关押的位置在第20行第20列;
同时求解上述两个问题;

二、解题思路

就是不断地dfs然后递归到终点,否则回退,再递归,再到终点的话就更新

三、代码实现

#if 1

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstring>
using namespace std;

const int N = 14;
const int MAZE_SIZE = 14;

//0为通路 1为墙壁 2为炸弹 3为大怪兽 4为小怪兽 6为传送门 8为终点
int maze[N][N] = {
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1},  //0
	{0,0,0,0,0,0,1,1,1,0,0,0,0,1},  //1
	{1,0,1,2,1,0,4,0,2,1,1,1,2,1},  //2
	{1,0,1,4,1,1,1,1,1,1,0,4,0,1},  //3
	{1,0,1,6,1,0,6,0,1,0,0,1,1,1},  //4
	{1,0,1,1,1,3,0,0,1,0,4,1,3,1},  //5
	{1,4,0,0,1,1,1,1,1,6,0,1,6,1},  //6
	{1,0,1,0,1,0,0,4,0,0,0,1,0,1},  //7
	{1,0,1,0,4,2,1,1,1,1,4,1,1,1},  //8
	{1,2,0,6,1,0,0,0,1,1,0,2,0,1},  //9
	{1,1,1,1,1,1,1,0,0,1,0,1,1,1},  //10
	{1,0,0,3,0,0,1,4,2,1,0,1,8,1},  //11
	{1,0,4,1,0,6,1,0,0,1,0,0,0,1},  //12
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1}   //13
};



int traverse[N];
vector<pair<int, int>> res;
vector<pair<int, int>> step;
int dir[4][2] = { 0,1,1,0,-1,0,0,-1 };
bool used[N][N];  

int hp_res = -1;

int get1(int x, int y)
{
	return x * 14 + y;
}

pair<int, int> get2(int n)
{
	pair<int, int> res;
	res.first = n / 14;
	res.second = n % 14;
	return res;
}

void init()
{
	//传送门
	//a[9,3] b[12,5] c[4,3] d[5,6] e[6,9] f[6,12]
	traverse[get1(9, 3)] = (get1(12, 5));
	traverse[get1(12, 5)] = (get1(9, 3));
	traverse[get1(4, 3)] = (get1(4, 6));
	traverse[get1(4, 6)] = (get1(4, 3));
	traverse[get1(6, 9)] = (get1(6, 12));
	traverse[get1(6, 12)] = (get1(6, 9));

	used[1][0] = true;
	step.push_back({ 1,0 });
}

void bomb(int x, int y)
{
	int dir[9][2] = { -1,-1,-1,0,-1,1,0,-1,0,0,0,1,1,-1,1,0,1,1 };
	for (int i = 0; i < 9; ++i)
	{
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];

		if (nx < 0 || nx >= MAZE_SIZE || ny < 0 || ny >= MAZE_SIZE) continue;

		maze[nx][ny] = 0;
	}
}

void dfs(int startx, int starty, int cur_hp)
{
	if (cur_hp < 0) return;
	if (hp_res != -1 && cur_hp < hp_res) return;

	for (int i = 0; i < 4; ++i)
	{
		int nx = startx + dir[i][0];
		int ny = starty + dir[i][1];

		if (nx < 0 || nx >= MAZE_SIZE || ny < 0 || ny >= MAZE_SIZE) continue;
		if (used[nx][ny] || maze[nx][ny] == 1) continue;

		if (maze[nx][ny] == 0)  //通路
		{
			used[nx][ny] = true;
			step.push_back({ nx,ny });

			dfs(nx, ny,cur_hp);

			used[nx][ny] = false;
			step.pop_back();
		}
		else if (maze[nx][ny] == 2)  //炸弹
		{
			used[nx][ny] = true;
			int backup[N][N] = {0};
			memcpy(backup, maze, sizeof maze);
			bomb(nx, ny);
			step.push_back({ nx,ny });

			dfs(nx, ny,cur_hp-10);

			used[nx][ny] = false;
			step.pop_back();
			memcpy(maze, backup, sizeof maze);
		}
		else if (maze[nx][ny] == 3)  //大怪兽
		{
			used[nx][ny] = true;
			maze[nx][ny] = 0;
			step.push_back({ nx,ny });

			dfs(nx, ny,cur_hp - 20);

			used[nx][ny] = false;
			step.pop_back();
			maze[nx][ny] = 3;
		}
		else if (maze[nx][ny] == 4)  //小怪兽
		{
			used[nx][ny] = true;
			maze[nx][ny] = 0;
			step.push_back({ nx,ny });

			dfs(nx, ny,cur_hp-5);

			used[nx][ny] = false;
			step.pop_back();
			maze[nx][ny] = 4;
		}
		else if (maze[nx][ny] == 6)  //传送门
		{
			used[nx][ny] = true;
			int t = get1(nx, ny);
			pair<int, int> next = get2(traverse[t]);
			step.push_back({ nx,ny });
			step.push_back({ next.first,next.second });

			dfs(next.first, next.second,cur_hp);

			used[nx][ny] = false;
			step.pop_back();
			step.pop_back();
		}
		else if(maze[nx][ny] == 8)  //终点
		{
			step.push_back({ nx,ny });
			if (cur_hp > hp_res)
			{
				hp_res = cur_hp;
				res = step;
			}
			step.pop_back();

			return;
		}

		
		
	}
}

int main()
{
	init();
	dfs(1, 0,100);
	if (hp_res <= 0)
	{
		cout << "false" << endl;
	}
	else
	{
		cout << "true" << endl;
		cout << hp_res << endl;
		int cnt = 1;
		for (int i = 0; i < res.size(); ++i)
		{
			printf("(%02d,%02d)", res[i].first, res[i].second);
			if (cnt % 10 == 0) puts("");
			else if(i != res.size() - 1) printf("->");
			cnt++;
		}
	}
	
	return 0;
}

#endif

四、测试

在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_60033897/article/details/135051930
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。