[数据结构与算法]（新版）SJTU-OJ-1029. 深度优先搜索问题

题目描述

有一个6*6的棋盘，每个棋盘上都有一个数值，现在又一个起始位置和终止位置，请找出一个从起始位置到终止位置代价最小的路径：

1. 只能沿上下左右四个方向移动
2. 总代价是没走一步的代价之和
3. 每步（从a,b到c,d）的代价是c,d上的值与其在a,b上的状态的乘积
4. 初始状态为1

每走一步，状态按如下公式变化：（走这步的代价%4）+1。

输入格式

第一行有一个正整数n，表示有n组数据。

每组数据一开始为6*6的矩阵，矩阵的值为大于等于1小于等于10的值，然后四个整数表示起始坐标和终止坐标。

输出格式

输出最小代价

样例输入

1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 5 5

样例输出

23

数据范围

(无)

深度优先搜索 DFS

?????? DFS【Deep First Search】,利用递归函数，一头往一个方向撞下去，不撞到南墙不死心那种，一旦有障碍就缩回去，调头，换方向。
??????关键：要有一个bool数组，记录已经走过的路，而且注意！在退回来的时候要修改bool数组的内容。

		book[ntx][nty] = 1;				// 要去坐标为（ntx，nty）的位置，数组上标记一下
       	thiscost = testmap[ntx][nty] * state;
        dfs(ntx, nty, thiscost % 4 + 1, cost + thiscost);
        book[ntx][nty] = 0;				// 函数运行完了，原路退回，bool数据记得恢复

??????问题：为什么要不断改这个 bool 数组的值？
??????解答：DFS本质是尝试，一个劲的尝试，比如我规定顺序{东，南，西，北}，好，那么从起点开始，我就向东，看看能不能走，可以的话就向东，然后检测有没有到终点，没有到终点，继续递归，再看看能不能往东走，不行就尝试下一个，向南走，然后检测有没有到终点，没有到就继续尝试看能不能向东走……（人类的本质就是复读，你觉得呢）
??????一旦到了终点，好耶，找到一条路，然后呢，怎么办比较一下看看和已找到的路相比哪个更近一些，如果发现更近的那就要更新结果。然后呢，然后要退回去，回到哪，回到起点，当然函数不会调头，只会默默的结束运行，每一个内层函数结束后，运行的第一个语句是什么？book[ntx][nty] = 0; 之前标记为已经走过的路，现在撤销标记，这是DFS的关键核心！
??????问题：如何优化DFS？
??????解答：剪支！见下，如果在走的途中花费已经超过之前找到的答案，直接停止运行不用找了，没有浪费时间的必要。

 if (cost > result)
        return;

题目解答

??????还是回归递归函数的本质，模拟一个过程，同理我们这个题目也是，模拟的就是走一步的过程，递归结束的条件是什么？到终点。递归传递的参数是什么？坐标，状态，花费的代价。

#include <iostream>
#include <string.h>
#include <limits.h>
using namespace std;
int testmap[6][6];
int book[6][6] = {0};
int stx, sty, edx, edy;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int result;

// 注意，每次调用dfs函数前要result = INT_MAX;
void dfs(int nx, int ny, int state, int cost)
{
    int ntx, nty,thiscost;
    if (nx == edx && ny == edy)
    {
        if (cost < result)
        {
            result = cost;
        }
        return;
    }

    if (cost > result)
        return;

    for (int i = 0; i < 4; i++)
    {
        ntx = nx + dx[i];
        nty = ny + dy[i];
        if (ntx >= 6 || ntx < 0 || nty >= 6 || nty < 0)
        {
            continue;
        }
        if (book[ntx][nty] == 0)
        {
            book[ntx][nty] = 1;
            thiscost = testmap[ntx][nty] * state;
            dfs(ntx, nty, thiscost % 4 + 1, cost + thiscost);
            book[ntx][nty] = 0;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    // 下面开始循环n次
    while(n--)
    {
        memset(book,0,sizeof(book));
        result = INT_MAX;
        for (int i = 0; i < 6; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                cin >> testmap[i][j];
            }
        }
        cin >> stx >> sty >> edx >> edy;
        dfs(stx, sty, 1, 0);
        cout << result;
        // 上面需要循环n次
    }
    system("pause");
    return 0;
}