题目分析

一道很典型的dfs模板题。 我们只要从起点出发进行深度优先搜索就行了，如若没有搜到终点那就是无喽

解题思路

很多大佬已经讲过了

我主要是想谈一下具体实现的小细节

1. 边界表示

本人采用给地图围一圈围墙('x')的方法来表示边界，也可以省去后续的一些判断,有x的地方不踩就行，边界、障碍物和访问过的地方都可以通过判断是否'x'的方式来决定踩不踩

//在地图外围包一层障碍物。可以省去出界的判断
for(int i = 0;i <= n+1;++i)
{
    maze[i][0] = 'x';
    maze[i][m+1] = 'x';
}

for(int i = 0;i <= m+1;++i )
{
    maze[0][i] = 'x';
    maze[n+1][i] = 'x';
}

2. 已访问节点的表示

看到很多大佬都是用了一个visited数组来记录走过的地方，我觉得可以直接放个路障'x'在上面,可以节省一个数组并化简后续判断

maze[x][y] = 'x';

效果:

//判断此路通不通
if(maze[X][Y] != 'x')
    traverse(X,Y);

完整代码(递归版本)

因为本人比较菜，有时候看大牛的代码会有些脑子跟不上。我这里考虑到跟我一样的朋友们，我整理了代码，尽量用比较清晰的表示方式，并写了必要的注释，希望对新手朋友们有帮助

#include <iostream>
#include <algorithm>
using namespace std;

char maze[502][502];
int n,m;

//四个移动方向
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int startX,startY;
bool flag;

void traverse(int x,int y);;

int main(void)
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        flag = 0;
        
        //在地图外围包一层障碍物。可以省去出界的判断
        for(int i = 0;i <= n+1;++i)
        {
            maze[i][0] = 'x';
            maze[i][m+1] = 'x';
        }

        for(int i = 0;i <= m+1;++i )
        {
            maze[0][i] = 'x';
            maze[n+1][i] = 'x';
        }

        for(int i = 1;i <= n;++i)
        {
            for(int j = 1;j <= m;++j)
            {
                cin >> maze[i][j];
                
                //记录起点位置
                if(maze[i][j] == 's')
                {
                    startX = i;
                    startY = j;
                }
            }
        }
        
        //开始遍历
        traverse(startX,startY);
        
        cout << (flag?"YES":"NO") << endl;
    }
    return 0;
}

void traverse(int x,int y)
{
    maze[x][y] = 'x'; //已访问，放个路障，下次不要走了
    int X,Y;
    for(int i = 0;i < 4 && !flag;++i) //若flag=1说明已经找到，没再搜下去的必要，早点回家洗洗睡
    {
        //得到下一个要访问的坐标
        X = x + dx[i];
        Y = y + dy[i];
        
        //判断是否到达终点
        if(maze[X][Y] == 't')
            flag = 1;
        
        //判断此路通不通
        if(maze[X][Y] != 'x')
            traverse(X,Y);
    }
}

踩坑:

之前马踏棋盘写魔怔了，本题我居然tm的回溯了(打自己

我们不需要具体路径，只需要知道起点终点是否连通

本题不用回溯也不可以回溯，回溯会超时，我甚至为此写了一版用栈,迭代模拟递归的代码，非常烂，但是也过了，贴下面，我就不整理了。

#include <iostream>
#include <stack>
#include <algorithm>

typedef long long ll;
using namespace std;

typedef struct _pos{
    int x;
    int y;
    int i;
}pos;

char maze[510][510];
int n,m,flag;
stack<pos> s;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};


int startX,startY;

void traverse(int x,int y);
void print(int n,int m);

int main(void)
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    while(t--)
    {
        flag = 0;
        while(!s.empty())
            s.pop();
        cin >> n >> m;
        for(int i = 0;i <= n+1;++i)
        {
            maze[i][0] = 'x';
            maze[i][m+1] = 'x';
        }

        for(int i = 0;i <= m+1;++i )
        {
            maze[0][i] = 'x';
            maze[n+1][i] = 'x';
        }

        for(int i = 1;i <= n;++i)
        {
            for(int j = 1;j <= m;++j)
            {
                cin >> maze[i][j];
                if(maze[i][j] == 's')
                {
                    startX = i;
                    startY = j;
                }
            }
        }
        // print(n,m);
        pos t;
        t.x = startX;
        t.y = startY;
        t.i = 0;
        s.push(t);

        traverse(startX,startY);
        cout << (flag?"YES":"NO") << endl;
    }
    return 0;
}

void traverse(int xx,int yy)
{
    pos t;
    int x,X;
    int y,Y;
    int i;
    while(!s.empty() && flag != 1)
    {
        // print(n,m);
        // cout << endl;

        pos top = s.top();
        s.pop();
        x = top.x;
        y = top.y;
        i = top.i;

        maze[x][y] = 'x';

        for(;i < 4;++i)
        {
            X = x+dx[i];
            Y = y+dy[i];

            if(maze[X][Y] == 't')
            {
                flag = 1;
                return;
            }

            if(maze[X][Y] == '.')
            {
                top.i = i+1;
                i=-1;

                t.x = X;
                t.y = Y;
                t.i = 0;

                s.push(top);
                s.push(t);
                break;
            }
        }
    }
}

void print(int x,int y)
{
    for(int i = 0;i <= x+1;++i)
    {
        for(int j = 0;j <= y+1;++j)
        {
            cout << maze[i][j] << ' ';
        }
        cout << endl;
    }
}