这题建议用BFS
by zhuzl009 @ 2023-03-29 20:32:39
@[zhangchengyi356535](/user/725397)
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int N = 2010;
int n, m;
bool vis[N][N], flag;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char c[N][N];
struct node {
int x, y;
int step;
} st;
bool check(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && c[x][y] != '#';
}
void bfs(node st) {
vis[st.x][st.y] = true;
queue<node> q;
q.push(st);
while (!q.empty()) {
node top = q.front();
q.pop();
for (int i = 0; i < 4; i ++) {
int x = top.x + dir[i][0];
int y = top.y + dir[i][1];
if (c[top.x][top.y] == 'd') {
cout << top.step;
flag = true;
return ;
}
if (check(x, y)) {
q.push({x, y, top.step + 1});
vis[x][y] = true;
}
}
}
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf ("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> c[i][j];
if (c[i][j] == 'm')
st = {i, j, 0};
}
}
bfs(st);
if (!flag)
cout << "No Way!";
return 0;
}
```
by zhuzl009 @ 2023-03-29 20:57:33