原题链接

最短路ＢＦＳ模型（０１距离）

#include <bits/stdc++.h>
#define x first
#define y secondusing namespace std;
const int N = 2010;
char g[N][N];
int dist[N][N];
bool st[N][N];
typedef pair<int, int> PII;
queue<PII> q;
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int bfs()
{int sx, sy, x2, y2;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )if(g[i][j] == 'm')  sx = i, sy = j;else if (g[i][j] == 'd')    x2 = i, y2 = j;memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[sx][sy] = 0;st[sx][sy] = true;q.push({sx, sy});while(q.size()){auto t = q.front();q.pop();if(t.x == x2 && t.y == y2)return dist[t.x][t.y];for (int i = 0; i < 4; i ++ ){int a = t.x + dx[i], b = t.y + dy[i];if(a < 1 || a > n || b < 1 || b > m || st[a][b] || g[a][b] == '#')  continue;st[a][b] = true;dist[a][b] = dist[t.x][t.y] + 1;q.push({a, b});}}return dist[x2][y2];
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++)cin >> g[i][j];int t = bfs();if(t == 0x3f3f3f3f) puts("No Way!");else    cout << t << endl;return 0;
}