```cpp#include <bits/stdc++.h>
using namespace std;
int n,m;
char mzc[2005][2005];
int xi,xj;
int sum=0;
int ans=114;
int fx[7]={0,1,0,-1,0};
int fy[7]={0,0,1,0,-1};
void dfs(int x,int y){
if(mzc[x][y]=='d') {
puts("1");
ans=min(ans,sum);
cout << ans << endl;
return;
}
if(mzc[x][y]=='#'||mzc[x][y]=='##'||x>n||x<1||y>m||x<1){
return;
}
mzc[x][y]='##';
for(int i=1;i<=4;i++){
int dx=x+fx[i];
int dy=y+fy[i];
sum++;
dfs(dx,dy);
sum--;
if(mzc[dx][dy]=='##') mzc[x][y]='.';
}
}
int main (){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> mzc[i][j];
if(mzc[i][j]=='m') {
xi=i,xj=j;
mzc[i][j]='.';
}
}
}
dfs(xi,xj);
if(ans==114) puts("No Way!");
else printf("%d",ans);
return 0;
}
by j_steady @ 2022-04-09 22:07:05
一个char变量你是怎么保存两个#的？
//当然可能是我孤陋寡闻太菜了那大家疯狂d我
by Xeqwq @ 2022-04-09 22:24:48
同上
by Mr_WA的大号 @ 2022-04-09 22:26:19
坏了
by j_steady @ 2022-04-17 09:33:33
这题dfs会t吗
by j_steady @ 2022-04-17 10:49:09
@[整活队长xeq](/user/229373) 这题dfs会t吗
by j_steady @ 2022-04-17 10:50:08
@[j_steady](/user/559503) 显然不会
by Xeqwq @ 2022-04-17 15:00:55
@[整活队长xeq](/user/229373) 可我t了
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m;
char mzc[2005][2005];
int xi,xj;
int sum=0;
int ans=114;
int fx[7]={0,1,0,-1,0};
int fy[7]={0,0,1,0,-1};
void dfs(int x,int y){
if(mzc[x][y]=='d') {
ans=min(ans,sum);
return;
}
mzc[x][y]='#';
for(int i=1;i<=4;i++){
int dx=x+fx[i];
int dy=y+fy[i];
if(mzc[dx][dy]=='#'||mzc[dx][dy]=='!'||dx>n||dx<1||dy>m||dy<1) continue;
sum++;
dfs(dx,dy);
sum--;
if(mzc[dx][dy]=='d') continue;
mzc[dx][dy]='.';
}
}
int main (){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> mzc[i][j];
if(mzc[i][j]=='m') {
xi=i,xj=j;
mzc[i][j]='.';
}
}
}
dfs(xi,xj);
if(ans==114) puts("No Way!");
else printf("%d",ans);
return 0;
}
by j_steady @ 2022-04-17 15:12:02
@[整活队长xeq](/user/229373) 机房的yy说这题是最短路不能dfs（
by j_steady @ 2022-04-17 15:12:56
能写吧是移动次数
要是真的不行就写最短路吧
by Xeqwq @ 2022-04-17 18:20:21