此贴不讲优化！！！
题目大意
从 (x_1,y_1) 走到 (x_2,y_2) 。 8 个方向。
思路
经典灵魂 3 连问。
- 边界；
- 走过；
- 墙；
代码：
if(xx<1||yy<1||xx>n||yy>m)continue;
if(vis[xx][yy]==1)continue;
if(c[xx][yy]=='#')continue;
因为是 \color{green}8 个方向，所以 \color{green}dx,dy 的初始值是：
- 上： dx-1,dy ；
- 下： dx+1,dy ；
- 左： dx,dy-1 ；
- 右： dx,dy+1 ；
- 左上： dx-1,dy-1 ；
- 右上： dx-1,dy+1 ；
- 左下： dx+1,dy-1 ；
- 右下： dx+1,dy+1 ；
代码：
int fx[8]={-1,1,0,0,-1,-1,1,1};
int fy[8]={0,0,-1,1,-1,1,-1,1};
因为有 8 个方向，且每个方向时间不同，所以：
- i<4 时间 +2 ；直着走。
- i>=4 时间 +3 ；斜着走。
代码：
if(i<4)
dfs(xx,yy,bs+2);
else
dfs(xx,yy,bs+3);
最后就是 vis ，也是最简单的部分。
- 走过 vis=1 ；
- 返回 vis=0 ；
整个 for 循环代码：
for(int i=0;i<8;i++){
int xx=x+fx[i],yy=y+fy[i];
if(xx<1||yy<1||xx>n||yy>m)continue;
if(vis[xx][yy]==1)continue;
if(c[xx][yy]=='#')continue;
vis[xx][yy]=1;
if(i<4)
dfs(xx,yy,bs+2);
else
dfs(xx,yy,bs+3);
vis[xx][yy]=0;
}
最后考虑到达目标：
- mina=-1 ，让他等于时间；
- 否则，让 mina 等于 mina 和 时间 的最小值。
代码：
if(x==zbnlx&&y==zbnly){
if(mina==-1)mina=sj;
else mina=min(mina,sj);
}
最后是最终代码：
#include<bits/stdc++.h>
using namespace std;
int fx[8]={1,-1,-1,1,0,0,-1,1};
int fy[8]={1,-1,1,-1,-1,1,0,0};
int vis[105][105]={0};
char c[105][105];
int n,m;int mina=-1;
int zbfbx,zbfby,zbzzx,zbzzy;int sf=0;
void dfs(int x,int y,int bs){
if(x==zbfbx&&y==zbfby){
if(mina==-1)mina=bs;
else mina=min(mina,bs);
}
for(int i=0;i<8;i++){
int xx=x+fx[i],yy=y+fy[i];
if(xx<1||yy<1||xx>n||yy>m)continue;
if(vis[xx][yy]==1)continue;
if(c[xx][yy]=='#')continue;
vis[xx][yy]=1;
if(i<4)
dfs(xx,yy,bs+3);
else
dfs(xx,yy,bs+2);
vis[xx][yy]=0;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
if(c[i][j]=='@')zbzzx=i,zbzzy=j;
if(c[i][j]=='%')zbfbx=i,zbfby=j;
}
}
dfs(zbzzx,zbzzy,0);
cout<<mina<<endl;
return 0;
}
后记
如果按此思路（Hard Version）可以得 {green}60 分。
60 分记录链接。
↑ ↑ ↑点这里。
回看题目。
详细吗
- 非常详细
- 详细
- 优秀
- 不详细
0
投票人
最后的最后
很有必要搞一个 `LaTeX大佬` 徽章 麻烦交一下意见，投个票，谢谢。