用DFS解决迷宫最短路径问题的一些思考

Some Words

摆烂了两天，才开始思考DFS究竟该怎么写出来。也是遇到了很多的问题。

比如如何表示方向呢，如何输出没有通路的条件……

现在也是写出来了，果不其然差一点超时。

毕竟DFS是找出所有通路后比较最小值的递归嘛

所以为什么还要学DFS

About Problem

直接去看上一篇post喵~

上一篇在这里喵~

Thinking Process about this problem

DFS若是寻找最优解的化必不可少的便是循环或者递归。

循环不知道要穷举多少例子，而递归似乎是个不错的方法。

通过step计数，在起点的时候为1，每走到一层便step加1，使其中遇到的第一个节点成为新的起点递归，直到终点停止。通过for循环转变方向继续递归，若是能到终点便比较step与min。最后记录下来最短路径

若是没有通路，则记录最短路径的容器为空（以此便可作为条件了）。

好了，看文字基本没什么用，还是分析代码有意思(●ˇ∀ˇ●)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int m, n, Min = 98769954;
int a[1005][1005];
int vis[1005][1005];
typedef struct point
{
    int x3, y3, d3;
} Point;
Point path[100010];
Point shortest_path[10010];
int moves[4][2] = { {0,1},{1,0 },{0,-1},{-1,0} };
void dfs(int x, int y, int step)
{
    if (x == m && y == n)
    {
        if (step < Min)
        {
            Min = step;
            for (int i = 0;i < step;i++)
            {
                shortest_path[i] = path[i];
            }
        }
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nx = x + moves[i][0];
        int ny = y + moves[i][1];
        if (nx<1 || nx>m || ny<1 || ny>n) continue;
        if (vis[nx][ny] == 0 && a[nx][ny] == 1)
        {
            vis[nx][ny] = 1;
            path[step].x3 = nx;
            path[step].y3 = ny;
            path[step].d3 = i+1;
            dfs(nx, ny, step + 1);
            vis[nx][ny] = 0;
        }
    }
    return;
}
int main()
{
     
    while (scanf("%d%d", &m, &n))
    {
        if (m == 0 && n == 0) {
            return 0;
        }
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                scanf("%d", &a[i][j]);
            }
        vis[1][1] = 1;
        path[0] = { 1,1 };
        dfs(1, 1, 1);
        int count = 0;
        if (shortest_path[0].x3 == 0 && shortest_path[0].y3 == 0)
        {
            cout << "没有通路" << endl;
        }
        else
        {
            for (int i = 0;i <= Min - 1;i++)
            {
                if (i != Min - 1) {
                    printf("(%d,%d,%d)", shortest_path[i].x3, shortest_path[i].y3, shortest_path[i + 1].d3);
                    count++;
                }
                if (count == 5)
                {
                    cout << endl;
                    count = 0;
                }
                else if (i == Min - 1)
                {
                    printf("(%d,%d,%d)", shortest_path[i].x3, shortest_path[i].y3, 0);
                    cout << endl;
 
                }
 
            }
 
        }
        memset(shortest_path,'\0',sizeof(shortest_path));
        memset(path, '\0', sizeof(path));
        memset(vis, '\0', sizeof(vis));
        Min = 98769954;
 
    }
 
    }
 

Final

哎呀，又花了很多时间理解，这种找路径的问题再加上递归简直是折磨人。递归还是一如既往的折磨人啊，很难理解。

其实若是类比为数学归纳法的话便好理解一些了。

首先写出Base case。在递归中便是递归最基本的情况。有时是起点，而有时候又会是重点，但不变的是，它一定是约束函数中变量的条件。

其次便开始思考n或者n+1的情况，n如何到n+1，甚至于起点如何到终点。这之间过程的模拟需要不断利用该函数进行模拟（好像链表一样)

(很烂的比喻）