先看题目：https://ac.nowcoder.com/acm/problem/14572
题目描述：
小明要从'S'出发。他只能往上下左右四个方向移动。问是否可以到达'E' ？
解题思路：
雨巨上课的例题，有几个技巧值得学习：
1.scanf(" %c",&c);可以直接忽略回车等
2.可以通过对二维数组方格来编号i*m+j，来避免使用结构体或pair来记录。

这题n,m不超过500。实际上dfs剪枝后也能过。
先上bfs代码：

#include<bits/stdc++.h>
using namespace std;
bool mp[510][510];
int n, m, s, t;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int dis[510][510];
queue<int> q;
int bfs(int s, int t)
{
    while(!q.empty()) q.pop();
    q.push(s);
    while(!q.empty()) {
        int tmp = q.front();
        q.pop();
        int x = tmp / m;
        int y = tmp % m;
        for(int i = 0; i < 4; i++){
            int dx = x+dir[i][0];
            int dy = y+dir[i][1];
            if(dx < 0 || dy < 0 || dx >= n || dy >= m) continue;
            if(mp[dx][dy] == 0) continue;
            if(dis[dx][dy] != 0) continue;
            if(dx*m+dy == t) return 1;
            dis[dx][dy] = dis[x][y] + 1;
            q.push(dx*m+dy);
        }
    }
    return 0;
}

int main()
{
    while(scanf("%d%d",&n,&m) != EOF) {
        memset(mp, 0, sizeof(mp));
        memset(dis, 0, sizeof(dis));
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++) {
                char c;
                scanf(" %c",&c);
                if(c == 'S') {s= i*m + j; mp[i][j] = 1;}
                else if(c == 'E') {t= i*m + j; mp[i][j]=1;}
                else if(c == '.') {mp[i][j] = 1;}
                else if(c == '#') {mp[i][j] = 0;}
            }
        if(bfs(s, t)) printf("Yes\n");
        else printf("No\n");
    }
}

但看到有dfs代码也能过，这是因为vis数组没有还原，走过的点不走第二遍。因为也不需要走第二遍。某个点从左边过去然后他走不到终点，换个方向过去也走不到终点的。举个例子，a 到b b走不到终点 那么换个别的方向到了b也还是走不到终点。所以每个点只需走一遍即可。这是没有明着剪 但是实际上剪了枝。

dfs部分代码如下：

int sx,sy,ex,ey;
char mp[510][510];
int vis[510][510];
int d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};

void dfs(int x,int y)
{
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int fx=x+d[i][0];
        int fy=y+d[i][1];
        if(fx>=1&&fx<=n&&fy>=1&&fy<=m&&mp[fx][fy]!='#'&&vis[fx][fy]!=1)
        {
            if(mp[fx][fy]=='E')
            {
                ans=1;
                return ;
            }
            dfs(fx,fy);
        }
    }
    return ;
}