洛谷 P2689 東南西北【模擬/搜索】

題目描述

給出起點和終點的坐標及接下來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\n",&t); way[i]=getnum(t); //將每一秒的風向儲存好。
    }dfs(startx,starty,0,1);if(ans==999999) //如果ans還是999999，就說明到不了。
    {puts("-1");}else{printf("%d",ans);}return 0;
}

?