接下来，小A就将操控艾吉奥从佛罗伦萨庄园出发，前往梵蒂冈，夺取教皇权杖。
在整个过程中，每经过一个建筑，都需要花费一定的时间，需要特别注意的是，由于圣母百花大教堂、圣马可大教堂、乔托钟楼都有众多圣殿骑士守护，经过这三个地方时，你需要花费100的时间
小A已经急不可耐地想要通关了，所以希望花费最少的时间到达梵蒂冈，请你帮他计算一下，从佛罗伦萨庄园到梵蒂冈，最快需要多少时间？
输入描述:
第一行有两个整数，表示地图的行数n和列数m，地图为一个n×m的矩阵
接下来有n行，每行m个字符，每个字符是一个数字或大写字母，数字表示经过该建筑需要的时间，字母表示特定建筑（S表示佛罗伦萨的庄园，即起点；E表示梵蒂冈，即终点；A表示圣母百花大教堂；B表示圣马可大教堂；C表示乔托钟楼；A、B、C在每组数据中至多出现一次），每个字符或数字之间用空格分隔
为了降低游戏难度，小A特意调小了地图
0≤n,m≤30
输出描述:
输出一个整数，从佛罗伦萨庄园到梵蒂冈的最小用时T

输入
3 3
S A E
1 2 3
1 B 3

输出
6

PS：起初看到这个题目我就想着一定是一个bfs的题，后面看大佬们的题解，发现大家都是用的dijkstra算法去做，因为求的是最短路嘛，但是因为这个题目的特殊性，dfs，bfs也可以用来求解最短路径，所以我就想每种方法都用一次

BFS+优先队列

bfs代码很形象就是首先把起点放入队列然后依次遍历这个点的周围四个点，然后放入队列，因为用了优先队列的优化，所以每次取栈顶元素（最小值）作为下一个遍历的起始点，然后依次按照之前的遍历，一旦遇到终点就返回最短路的值，还要判断一下边界，因为我们不能走出这个图！这个与dfs是一样的
其次这里我们用了一个小技巧去处理字符问题，为了不让回车和空格对我们所输入字符的干扰，我们在每次输入字符的前面加一个空格，这个它就会自动略去其他字符，当然也可以用c++标准输入输出，c++输入不会输入回车和空格字符。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
char c[maxn][maxn];
int sx, sy, ex, ey, n, m;
int d[4][2] = {
   1, 0, -1, 0, 0, 1, 0, -1};
int vis[maxn][maxn], b[maxn][maxn];
struct node
{
   
   int x, y, d;
   node(int xx, int yy, int dd) : x(xx), y(yy), d(dd) {
   }
   bool operator<(const node xx) const
   {
   
      return d > xx.d;
   }
};
int bfs(int x, int y)
{
   
   priority_queue<node> q;
   q.push(node(x, y, 0)); //首先把起点放入队列
   vis[x][y] = 1;
   while (!q.empty())
   {
   
      node xx = q.top();
      q.pop();
      if (xx.x == ex && xx.y == ey) //如果遇到了终点那么就返回当前距离
         return xx.d;
      for (int i = 0; i < 4; ++i) //依次遍历该点的上下左右节点
      {
   
         int nx = xx.x + d[i][0];
         int ny = xx.y + d[i][1];
         if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny]) //判断边界
         {
   
            int h = xx.d + b[nx][ny]; //当前距离加上下一个的距离
            vis[nx][ny] = 1;
            q.push(node(nx, ny, h));
         }
      }
   }
}
int main()
{
   
   while (~scanf("%d%d", &n, &m))
   {
   
      for (int i = 1; i <= n; ++i)
         for (int j = 1; j <= m; ++j)
         {
   
            scanf(" %c", &c[i][j]); //这是一个小技巧，防止换行符和空格符号的干扰
            if (c[i][j] == 'S')
               sx = i, sy = j;
            else if (c[i][j] == 'E')
               ex = i, ey = j;
            else if (c[i][j] == 'A' || c[i][j] == 'B' || c[i][j] == 'C')
               b[i][j] = 100;
            else
               b[i][j] = c[i][j] - '0';
         }
      printf("%d\n", bfs(sx, sy));
   }
}

DFS

dfs就是深度优先搜索，一条路走到黑，知道走到不能走为止，所以我们需要剪枝！！我们每走过一个点就要标记一次，递归是一层一层递归的，只要走过就标记，当然回退到上一次的话，就要把之前标记过的清除，因为要进行新的一轮递归。

#include <bits/stdc++.h>
using namespace std;
int a[100][100], vis[100][100];
int sx, sy, ex, ey, n, m;
int inf = 0x3f3f3f3f;
int d[4][2] = {
   -1, 0, 1, 0, 0, -1, 0, 1};
int xx[4] = {
   -1, 1, 0, 0}, yy[4] = {
   0, 0, -1, 1};
char c;
void dfs(int x, int y, int sum)
{
   
   if (x == ex && y == ey)
   {
   
      inf = min(sum, inf);
      return;
   }
   if (sum >= inf)
      return;
   for (int i = 0; i < 4; ++i)
   {
   
      int nx = x + d[i][0];
      int ny = y + d[i][1];
      if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny])
      {
   
         vis[nx][ny] = 1;
         dfs(nx, ny, sum + a[nx][ny]);
         vis[nx][ny] = 0;
      }
   }
}
int main()
{
   
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j)
      {
   
         cin >> c;//c++输入语言默认是不输入空格和回车的
         if (c == 'S')
            sx = i, sy = j;
         else if (c == 'E')
            ex = i, ey = j;
         else if (c == 'A' || c == 'B' || c == 'C')
            a[i][j] = 100;
         else
            a[i][j] = c - '0';
      }
   dfs(sx, sy, 0);
   printf("%d\n", inf);
}

dijkstra+堆优化

dijkstra做这道题确实没想到的，但是后面仔细想想，确实是这样，因为题目要求的是最短路嘛，dijkstra是求最短路最高效的算法之一了，不过这个代码教之前的代码来看确实有点麻烦，但是理解起来是可以的，基本操作和思路还是差不多的，唯一有点新颖的就是它将二维数组转化成一维数组去操作

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int d[4][2] = {
   -1, 0, 1, 0, 0, -1, 0, 1};
int a[maxn][maxn];
int vis[maxn], dis[maxn];
struct node
{
   
    int e, w;
    bool operator<(const node x) const
    {
   
        return w > x.w;
    }
};
priority_queue<node> q;
vector<node> w[maxn];
void dijkstra(int s)
{
   
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    node t1, t2;
    t1.e = s;
    t1.w = 0;
    dis[s] = 0;
    q.push(t1);
    while (!q.empty())
    {
   
        t1 = q.top();
        q.pop();
        if (vis[t1.e])
            continue;
        vis[t1.e] = 1;
        for (int i = 0; i < w[t1.e].size(); ++i)
        {
   
            int v = w[t1.e][i].e;
            if (!vis[v] && dis[v] > dis[t1.e] + w[t1.e][i].w)
            {
   
                dis[v] = dis[t1.e] + w[t1.e][i].w;
                t2.e = v;
                t2.w = dis[v];
                q.push(t2);
            }
        }
    }
}
int main()
{
   
    int n, m, s, e;
    char c;
    scanf("%d%d", &n, &m);
    int end = (n - 1) * m + m - 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
   
            cin >> c;
            if (c == 'S')
                a[i][j] = 0, s = i * m + j;
            else if (c == 'E')
                a[i][j] = 0, e = i * m + j;
            else if (c == 'A' || c == 'B' || c == 'C')
                a[i][j] = 100;
            else
                a[i][j] = c - '0';
        }
    node t;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            for (int k = 0; k < 4; ++k)
            {
   
                int x = i + d[k][0];
                int y = j + d[k][1];
                if (x < 0 || x >= n || y < 0 || y >= m)
                    continue;
                t.e = x * m + y;
                t.w = a[x][y];
                w[i * m + j].push_back(t);
            }
    dijkstra(s);
    printf("%d\n", dis[e]);
}