题目描述
给出起点和终点的坐标及接下来T个时刻的风向(东南西北)，每次可以选择顺风偏移1个单位或者停在原地。求到达终点的最少时间。
如果无法偏移至终点，输出“-1”。
输入输出格式
输入格式：
第一行两个正整数x1,y1，表示小明所在位置。
第二行两个正整数x2,y2，表示小明想去的位置。
第三行一个整数T，表示T个时刻。
第四至第N+3行，每行一个字符，表示风向，即东南西北的英文单词的首字母。
输出格式：
最少走多少步。
输入输出样例
输入样例#1：
1 1 2 2 5 E N W W N
输出样例#1：
2
输入样例#2：
1 1 2 2 1 W
输出样例#2：
-1
输入样例#3：
1 1 2 2 3 W W W
输出样例#3：
-1
说明
样例1：向东走一步，向南走一步。
样例2、3：无法到达。
1<=T<=50
东：East
南：South
西：West
北：North
【分析】：注意：风从哪里来，就叫什么风，就往相反的方向走。
这个题是一个简单的模拟和搜索；只需要关注你要往哪里走，走多少步。
将一个二维数组分解，得到初始点和终点四个值；
最短路径就是分开跳，直至跳完，在验证是否到了终点；
//搜索
【代码】：
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int a,x,y,xx,yy; char f[50]; int cnt=0; int main() { cin>>x>>y; cin>>xx>>yy; cin>>a; for(int i=1;i<=a;i++) { cin>>f[i]; if(x>xx&&f[i]=='S') { x-=1;cnt++;} if(x<xx&&f[i]=='N') { x+=1;cnt++;} if(y>yy&&f[i]=='W') { y-=1;cnt++;} if(y<yy&&f[i]=='E') { y+=1;cnt++;} } if(x!=xx||y!=yy) cout<<"-1"; else cout<<cnt; }
#include<iostream> #include<cstring> #include<cstdio> using namespace std; char t; //t用来输入方向。 int next[4][2]={{1,0},{0,1},{-1,0},{0,-1}},book[1000][1000],way[1000],startx,starty,endx,endy,n,i,ans=999999; //book用来标记一个点走没走过，way储存了每一秒的风向。 int min(int x,int y) { return x<y?x:y; } int getnum(char c) //这个函数用来判断是东西南北里的哪一项。 { if(c=='N') { return 0; } if(c=='E') { return 1; } if(c=='S') { return 2; } if(c=='W') { return 3; } } void dfs(int x,int y,int now,int step) //step是现在几秒了，now是步数。 { if(x==endx && y==endy) //如果到达。 { ans=min(ans,now); //更新答案 return; } if(step==n+1) //这里很重要，不然会RE。 { return; } int tx,ty,k; k=way[step]; tx=x+next[k][0]; ty=y+next[k][1]; if(tx>=1 && tx<=n && ty>=1 && ty<=n && book[tx][ty]==0) //如果这一秒风吹我走没有越界也没有来过这就代表可以走 { book[tx][ty]=1; //标记这儿我已走过了。 dfs(tx,ty,now+1,step+1); //步数加一，秒数加一 book[tx][ty]=0; //回溯 } dfs(x,y,now,step+1); //就是这一秒我不走。 return; } int main() { scanf("%d %d",&startx,&starty); scanf("%d %d",&endx,&endy); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%c ",&t); way[i]=getnum(t); //将每一秒的风向储存好。 } dfs(startx,starty,0,1); if(ans==999999) //如果ans还是999999，就说明到不了。 { puts("-1"); } else { printf("%d",ans); } return 0; }