洛谷P2689 东南西北

https://www.luogu.org/problemnew/show/P2689

#include<iostream>
#include<algorithm>
using namespace std;
int sx,sy,ex,ey,t,ans=1e9;//sx和sy为小明所在位置,ex和ey为小明想去的位置,ans为步数
char a[];//风向
void dfs(int step,int x,int y,int i){//深搜函数,step为当前步数,x和y为当前坐标,i是a数组下标
if(x==ex&&y==ey){//判断当前坐标是否为小明想去的位置
ans=min(ans,step);//ans变为当前步数和ans的较小值
return;//返回
}
if(i>t) return;
if(step>ans) return;//剪枝,如果当前步数大于当前最优解,就没有必要接着往下搜,返回上一步
if(a[i]=='E'&&x<ex) dfs(step+,x+,y,i+);//判断当前x坐标是否在终点的x坐标的左边,如果是就往东(右)走,如果不是就不执行,不然可能会越走越远
if(a[i]=='W'&&x>ex) dfs(step+,x-,y,i+);
if(a[i]=='S'&&y>ey) dfs(step+,x,y-,i+);
if(a[i]=='N'&&y<ey) dfs(step+,x,y+,i+);
dfs(step,x,y,i+);//留在原地,记住步数不能加一,我被这个坑了一次...
}
int main(){
cin>>sx>>sy>>ex>>ey>>t;//输入
for(int i=;i<=t;i++){
cin>>a[i];//输入风向
}
dfs(,sx,sy,);//从起始坐标开始搜索,步数从0开始
if(ans==1e9) cout<<-;//如果ans依然等于初始值,则说明无法到达,输出-1
else cout<<ans;//输出最少步数
return ;
}

凑这么多字不容易啊...

上一篇:Lodop打印控件设置表格次页偏移


下一篇:Openjudge 1.3-04 垂直直方图