bfs/dfs/dijkstra +优先队列

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

解法一：BFS+优先队列

#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的代码思路和bfs差不多，一个用队列一个用递归

#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

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