[数据结构与算法]（新版）SJTU-OJ-1028. 采购

题目描述

skytim是伟大帝国UDF的首脑。作为一国的领袖，skytim很早就认识到一国的交通对经济建设的重要性。于是他要求UDF国内的建筑排成m*n的网络，道路建设在建筑的上方，并且每条道路都连接着两个有公共边的建筑。如下图所示：

这天是UDF国建国110周年纪念日，skytim正在主持盛大的阅兵式。随着“同志们好！”“首长好！”的声响此起彼伏，skytim的手机突然响了，是他的夫人Cyning打来的。

“skytim你早饭煮烂了，快给我回来！”

“啊？我还在阅兵呢！”

“我不管你现在在哪里，现在马上给我回来！”

“嗯，我现在马上回去！”

“回来记得顺路帮我买一把油纸伞。我要撑着它走过那条雨巷。好想知道成为戴望舒笔下那个丁香一样的结着愁怨的姑娘是一种怎样的体验。”

“行行行，随你。”

为了及时完成夫人的任务，skytim希望能够走一条最短的经过伞店的路径回家。但遗憾的是有些建筑正在施工，和它连着的道路都不能走。好在skytim早就对自己国家的地图烂熟于心，请你协助他找到最短的路径。

输入格式

输入第一行有两个整数n,m，表示地图的规模。

接下来m行每行n个数字，表示该建筑的状态。其中：

• 0表示普通建筑，可以经过。
• 1表示正在施工中的建筑，不可以经过。
• 2表示skytim阅兵的位置。
• 3表示skytim和Cyning的家。
• 4表示伞店。

输出格式

输出一个整数，表示skytim最少需要移动的距离。

样例输入

8 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0

样例输出

11

数据范围

对于 $40\%$ 的数据，$1\le n,m\le 10$?;

对于 $100\%$ ??的数据，$1\le n,m\le 1000$???;

关于本题

????????首先不得不说，这个题目是学习搜索很好的一个例题，题目的背景是地图问题，但是OJ上作业组也有很多数组地图系列的题目，方法都是一样的，所需要的知识包括一下内容：

• 数组（这个不会不用看了，回去看课本去）
• 函数的递归（程序设计知识）（深度优先搜索）
• 队的简单操作（数据结构知识）（广度优先搜索）

????????想要往下看的可以先对找上面的检查一下，其中第三点可以现学（现学就是可以，不要问我是怎么知道的，问就是我就是通过这个题目学会的queue的！）

关于搜索

????????搜索： 搜素这里介绍两种方法：广度优先搜索【BFS】 与 深度优先搜索【DFS】，顾名思义，广度优先搜索就是优先的覆盖面广的搜索，深度优先搜索就是优先搜索层次深的方法。如果是说地图上所有的地方都要搜索到的话，那么两个方法的时间复杂度是相同的。(我们假设搜索一个点的时间都是一样的，那么搜索区域大小一样，时间也一样)

广度优先搜索

????????广度优先搜索就像病毒一样，慢慢的向周围扩散，或者说是辐射，emmm，举个例字，下面这个图就是一张 $5\times 5$ 的地图，我们还是把这个表看做一个数组，左上角的坐标是 $（0,0）$，第一行中间的坐标记为$（0,3）$。
????????我们假设起点坐标是$（2,2）$，就是浅蓝色的0处，我们假设一次移动可以且仅可以有下面四种操作：整个地图没有障碍物！全部可以通行

• 向上一格
• 向下一格
• 向左一格
• 向右一格

???????那么我们可以得出，第一次走可以行进到黄色的区域
???????第二次走 最远 可以行进到黄色的区域。当然你也可以退回起点，这里我们只关注第 $i$ 次行走可以走到的最远的地方，把这些地方都进行标记（即赋值为对应的步数 $i$ ）那么显然，我们想要得知某个位置从出发点最少需要走多少距离，直接访问这个地方的标记 $i$ ，就可以得知到这个地方最少的步数！
???????第三次走 最远 可以行进到橙色的区域。
???????第四次走 最远 可以行进到绿色的区域。
???????……
???????以上这个过程我们就模拟了广度优先搜索的过程！
???????显然，搜索的过程要注意地图的边界，不能越界，数组的下标要自己保证合法性。

深度优先搜索

???????深度优先搜素就是利用函数的递归，一根筋往下走，遇到障碍或者到达终点，就回溯。（课本上结束回溯的时候说道，如果不行就返回到上一步，其实我个人觉得这个说法有点不合适，实际上就是没有通过 if 判断语句，所以什么也不做，等待这个 void 函数执行完毕，自动退出，就回溯到啦上一个步骤）
???????这里继续补充一下我对递归函数的思考，递归函数就是自己给自己挖一个洞，我调用我自己。【例如，下面的大圆圈表示第一次调用函数的函数入口，函数运行后又调用了自己，相当于大圆圈里面还有一个小圆圈，同理小圆圈继续调用自身这个函数，就形成了一个无底洞】。
???????显然这是不科学的！为了避免无底洞现象，必须设置终止的条件！！！

???????所以，写递归函数按照下面的语法来！可以避免无底洞现象。

void function(参数)
{
	// 写清楚终止条件
	if(终止条件)
		return;
	else
	// 根据实际情况情况调用自身这个函数
		function(参数);
}

???????这里再补充一下对递归函数的思考，也是一个认识广度优先搜索和深度优先搜索的区别：我们来看看下面这个函数：

void function(初始参数)
{
	if(终止条件)
		return;
	else
		function(参数1);	// 第一个递归函数
		function(参数2);	// 第二个递归函数
		function(参数3);	// 第三个递归函数
		
}

???????这个函数再运行的时候是怎么样的呢？显然，这一个函数可以导向三个自身的递归函数，那么导向这三个函数是同时的吗？显然不是，调用的时候先执行第一个语句：function(参数1); 然后进入到第二层函数，在第二层函数里面检查是否可以终止，不能终止就再一次的调用function(参数1); ，然后进入到第三层函数 $??$ ,一直执行到第 $n$ 层函数，终止条件满足，return;语句执行，【补：一旦执行 return; 语句，函数直接终止， return; 后面的语句都不会执行】然后退回到第 $n?1$ 层函数，执行function(参数2); // 第二个递归函数 ，然后再次递归，以此类推。
???????所以上面这个过程，本质就是深度优先搜索，不管远近，一头撞到底，（执行到函数终止）然后回溯到上一层函数，开始下一个函数的递归语句。

队、类的基本知识

???????队，顾名思义，把它理解成一个队伍就可以。【实际上是一种特殊的线性表】
???????第一，使用队的时候要包含头文件#include <queue>
???????第二，了解如何定义一个队，语法如下：

	queue<队伍元素的类型> 队名字

???????其中队伍元素的类型可以是int，double，或者是其他自定义的类型，为了便于后面的理解，我们先自定义一个类。【如果不懂类，可以把这个理解为一种或者多种类型集合，int，double都是一个类，还不懂可以继续看】
???????比如，我们要定义坐标这个类型，显然这个类型是c++之前我们没有接触过的，属于自定义的类，坐标这个类包括横坐标，纵坐标。横坐标数据类型是int， 纵坐标也是 int。类的定义方法如下

class 类型名 
{
	类型1	类型1的代表名
	类型2	类型2的代表名
	······
};

???????然后如果我们要定义坐标这个类,可以这样：node是节点，也是这个类型的名字，如果你不知道这个名字该怎么用，想想int 你是怎么在用的你一定就明白了。

class node
{
	int x;
	int y;
};

???????例如你要定义一个整型变量 a

int a;

???????同理，定义一个坐标点，在有了上面class的声明以后,我们可以定义一个坐标，下面这个代码就表示定义了两个个名字分别叫deparure，destination的点

node deparure,destination;

???????然鹅deparure里面包括横坐标纵坐标，所以我们可以通过下面的方法访问 deparure.x,deparure.y，.表示里面的一个分支，下面举个例子赋值。

	deparure.x = 1;
	deparure.y = 2;

???????说了这么多类的知识，我们还是回到队里面来，hhh队，例如我们定义一个名字叫做 bfsqueue 的队伍，队伍里元素都是 node 类型（我们刚刚定义过）

	queue<node> bfsqueue;

push 函数

???????用途：在队尾插入一个元素
???????函数传入参数：要插入的那个元素
???????函数返回值：无
???????举例：把 departure 这个元素放在队尾

	bfsqueue.push(departure);	// 括号里面的这个元素进入队尾

pop 函数

???????用途：踢出队伍最前面的元素。
???????函数传入参数：无。
???????函数返回值：无
???????举例：踢出bfsqueue 队伍里面最靠前的元素

	bfsqueue.pop();	// 队伍最前面的元素出队！

size 函数

???????用途：统计元素个数
???????函数传入参数：无。
???????函数返回值：unsigned int 一个正整数。
???????举例：统计bfsqueue 队伍里面元素个数,并输出：

	cout << bfsqueue.size();	// 队伍最前面的元素出队！

empty 函数

???????用途：判断队伍里面是否元素个数为0。
???????函数传入参数：无。
???????函数返回值：true 或者 false
???????举例：判断bfsqueue 队伍是否为空,非空则执行语句A;

	if(!bfsqueue.empty())
		A;

front 函数

???????用途：返回队列中第一个元素，但是并没有剔除。
???????函数传入参数：无。
???????函数返回值：队列中第一个元素
???????举例：把队列中第一个元素赋值给我们之前定义的 destination 这个变量。

	destination = bfsqueue.front();

back 函数

???????用途：返回队列中最后一个元素，但是并没有剔除。
???????函数传入参数：无。
???????函数返回值：队列中最后一个元素
???????举例：把队列中最后一个元素赋值给我们之前定义的 departure 这个变量。

	departure = bfsqueue.back();

题目解答

???????首先这个题目是个模板题，没有学过的可以利用这个机会学会广度优先搜索，之前也自己脑补过写代码写了几百行都模拟不出来，所以，还是直接学习吧！先上AC代码！

// 所有坐标x代表行数，y代表列数！
// 本题坐标采用0-base！

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;

class shop
{
    public:
        int x;
        int y;
};

class node
{
    public:
        int x;
        int y;
}sh[1000000] = { 0,0 };

int testmap[1010][1010];
int step[1010][1010];
// 定义增量x，y 数组，
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
// 定义shop数组

int shopnum = 0;
int m, n;

bool bfs_CheckNextstep(node checkobject)
{
    if (checkobject.x < 0 || checkobject.x >= m)
        return false;
    if (checkobject.y < 0 || checkobject.y >= n)
        return false;
    if (testmap[checkobject.x][checkobject.y] == 1)
        return false;
    if (step[checkobject.x][checkobject.y] != 0)
        return false;
    else
        return true;
    // if (nxt.x >= 0 && nxt.x < m && nxt.y >= 0 && nxt.y < n && step[nxt.x][nxt.y] == 0 && testmap[nxt.x][nxt.y] != 1)
    //     return true;
    // else
    //     return false;
}

// 广度优先搜索，传入的时候传入一个节点node！
void bfs_Main(node departure)
{
    memset(step, 0, sizeof(step));
    // 首先定义一个队列！
    queue<node> bfsque;
    bfsque.push(departure);
    node currentplace, nextplace;
    while (!bfsque.empty())
    {
        currentplace = bfsque.front();
        bfsque.pop(); // 把最前面的元素弹出去！
        for (int i = 0; i < 4; i++)
        {
            nextplace.x = currentplace.x + dx[i];
            nextplace.y = currentplace.y + dy[i];
            if (bfs_CheckNextstep(nextplace) == true)
            {
                step[nextplace.x][nextplace.y] = step[currentplace.x][currentplace.y] + 1;
                bfsque.push(nextplace);
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    node departure, destination;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> testmap[i][j];
            if (testmap[i][j] == 2)     
            {
                departure.x = i;
                departure.y = j;
            }
            if (testmap[i][j] == 3)     
            {
                destination.x = i;
                destination.y = j;
            }
            if (testmap[i][j] == 4)     
            {
                sh[shopnum].x = i;
                sh[shopnum].y = j;
                shopnum++;
            }
        }
    }

    int a[10000] = {0};
    int b[10000] = {0};
    bfs_Main(departure);
    for (int i = 0; i < shopnum; i++)
    {
        a[i] = step[sh[i].x][sh[i].y];
    }

    bfs_Main(destination);
    for (int i = 0; i < shopnum; i++)
    {
        b[i] = step[sh[i].x][sh[i].y];
    }

    long int ans = 1e8;
    long int temp;
    for (int i = 0; i < shopnum; ++i) 
    {
        if (a[i] > 0 && b[i] > 0)
        {
            temp = a[i] + b[i];
            ans = min(ans, temp);
        }  
    }
    cout << ans;
    system("pause");
    return 0;
}