没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全18342075 米家龙第四章1

18342075 米家龙第四章1

需积分: 0 0 下载量 99 浏览量 2022-08-03 10:46:54 上传评论收藏 443KB PDF 举报

温馨提示

试读

15页

1. 实验题目 2. 实验目的 3. 程序设计 1. 对当前 P 位置的上、下、左、右四种方向进行循环 2. 在进行一个方向移动的时候，判断下一

资源详情

资源评论

资源推荐

年级 2018 专业（方向）软件工程

学号 18342075 姓名米家龙

电话 18566916535 Email [email protected]om

开始日期 2020-07-09 完成日期 2020-07-10

中山大学数据科学与计算机学院本科生实验报

告

课程名称：算法设计与分析

任课教师：张子臻

第1题

1. 实验题目

1215 脱离地牢

2. 实验目的

熟悉并了解搜索的相关操作：

广度优先搜索 bfs

深度优先搜索 dfs

3. 程序设计

该题为最短路问题，并且每一步代价相同，可以通过搜索解决。

如果使用 dfs ，那么会因为“反复横跳”——两个位置来回移动可能导致无效操作太多（这点可以通

过记录当前位置的状态来解决），并且由于步数最大为255，会使得递归层数过高导致内存开销

大，运行时间长

使用 bfs ，通过循环进行搜索，通过时间增大减少内存开销

关于状态：由于 P 的每一步会影响到 P 和 H 两个的状态，因此状态的记录需要变成 (Px, Py, Hx,

Hy) ，从而记录该位置的状态

相关定义：

// 定义上下左右

#define UP 'N'

#define DOWN 'S'

#define LEFT 'W'

#define RIGHT 'E'

// 定义墙|熔浆|通路

#define WALL '#'

#define MELT '!'

拿到地图后，需要寻找到 P 和 H 的坐标信息：

#define ROAD '.'

// 定义两个人

#define Paris 'P'

#define Helen 'H'

const int maxn = 21;

vector<string> map;        // 地图

int n, m;             // 地图的行，列

const string MOVE_ACTION = "NSWE"; // 运动的操作

string H_way = "";         // 表示 H 的运动

int res[maxn][maxn][maxn][maxn];  // 记录当前位置的状态

struct Node

{

int Px, Py, Hx, Hy;

// 初始化

Node(int Px, int Py, int Hx, int Hy) : Px(Px), Py(Py), Hx(Hx), Hy(Hy) {}

};

queue<Node> q;

// 初始化储存状态的四维数组

void init()

{

for (int i = 0; i < maxn; i++)

{

 for (int j = 0; j < maxn; j++)

 {

  for (int k = 0; k < maxn; k++)

  {

   for (int l = 0; l < maxn; l++)

   {

    res[i][j][k][l] = -1;

    // cout << res[i][j][k][l] << ' ';

   }

  }

 }

}

void FindLocation(int &Px, int &Py, int &Hx, int &Hy, int n, int m)

{

for (int i = 0; i < m; i++)

{

 for (int j = 0; j < n; j++)

 {

  // cout << map[i][j] << endl;

  if (map[i][j] == Paris)

  {

   Px = i;

   Py = j;

   map[i][j] = '.'; // 清除位置

  }

  else if (map[i][j] == Helen)

  {

移动相关，用于计算横纵坐标的函数，定义从上到下为横坐标正方向，定义从左往右为纵坐标正方向：

关于状态：

1. 对当前 P 位置的上、下、左、右四种方向进行循环

2. 在进行一个方向移动的时候，判断下一个位置是否能够到达

如果能够达到，则通过 H_way 判断 H 的下一个位置是否能够到达

如果是 . ，则可以到达，然后判断两者位置是否重合，是则返回结果，否则进行递

归

如果是 ! ，则跳过，进入下一次循环

如果是 # , 则不动，然后判断两者位置是否重合，是则返回结果，否则进行递归

如果不能到达，则跳过，进入下一次循环

   Hx = i;

   Hy = j;

   map[i][j] = '.'; // 清除位置

  }

  if (Hx && Hy && Px && Py)

   return;

 }

}

int goX(int x, char positon)

{

int res = x;

if (positon == UP)

{

 res--;

 return res < 0 ? x : res; // 越界返回 x ，否则返回 res

}

if (positon == DOWN)

{

 res++;

 return res >= n ? x : res; // 越界返回 x ，否则返回 res

}

return x; // 移动指令不匹配

}

int goY(int y, char position)

{

int res = y;

if (position == LEFT)

{

 res--;

 return res < 0 ? y : res; // 越界返回 y ，否则返回 res

}

if (position == RIGHT)

{

 res++;

 return res >= m ? y : res; // 越界返回 y ，否则返回 res

}

return y;

}

int bfs(int Px, int Py, int Hx, int Hy)

剩余14页未读，继续阅读

内容反馈

艾苛尔

粉丝: 26
资源: 307

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

18342075 米家龙第四章1

评论0

最新资源

18342075 米家龙 第四章1

评论0

18342075米家龙第4次作业1

18342075 米家龙 第4次作业1

18342075米家龙1

18342075 米家龙1

18342075_米家龙1

18342075 米家龙 第二章1

18342075 米家龙 第一章2

18342075 米家龙 热身报告1

18342075米家龙实验3.cp1

18342075_米家龙_作业21

18342075米家龙实验2第1部分1

18342075米家龙实验2第2部分1

18342075米家龙实验41

18342075米家龙第2次书面作业1

2020-2stmt_18342075_米家龙_assign11

2020-2stmt_18342075_米家龙_assign41

18342075_米家龙_期末报告1

18342075_米家龙_作业11

18342075米家龙实验61

18342075米家龙实验一1

18342075米家龙实验51

18342075米家龙实验32

18342075米家龙理论课实验1

18342075-米家龙-计算机视觉期中作业-Edge detection1

2020-2stmt_18342075_米家龙_assign81

2020-2stmt_18342075_米家龙_assign31

2020-2stmt_18342075_米家龙_assign71

最新资源

18342075 米家龙第四章1

18342075 米家龙第4次作业1

18342075 米家龙第二章1

18342075 米家龙第一章2

18342075 米家龙热身报告1