免费软件下载网站入口正能量,北京网络维护公司,ai代码生成器,长沙seo推广外包题目描述 给出起点和终点的坐标及接下来T个时刻的风向(东南西北)#xff0c;每次可以选择顺风偏移1个单位或者停在原地。求到达终点的最少时间。 如果无法偏移至终点#xff0c;输出“-1”。 输入输出格式 输入格式#xff1a; 第一行两个正整数x1,y1#xff0c;表示小明所…题目描述 给出起点和终点的坐标及接下来T个时刻的风向(东南西北)每次可以选择顺风偏移1个单位或者停在原地。求到达终点的最少时间。 如果无法偏移至终点输出“-1”。 输入输出格式 输入格式 第一行两个正整数x1,y1表示小明所在位置。 第二行两个正整数x2,y2表示小明想去的位置。 第三行一个整数T表示T个时刻。 第四至第N3行每行一个字符表示风向即东南西北的英文单词的首字母。 输出格式 最少走多少步。 输入输出样例 输入样例#11 1
2 2
5
E
N
W
W
N 输出样例#12 输入样例#21 1
2 2
1
W 输出样例#2-1 输入样例#31 1
2 2
3
W
W
W 输出样例#3-1 说明 样例1向东走一步向南走一步。 样例2、3无法到达。 1T50 东East 南South 西West 北North 【分析】注意风从哪里来就叫什么风就往相反的方向走。 这个题是一个简单的模拟和搜索只需要关注你要往哪里走走多少步。 将一个二维数组分解得到初始点和终点四个值 最短路径就是分开跳直至跳完在验证是否到了终点 //搜索 【代码】 #includeiostream
#includecstring
#includecstdio
using namespace std;
int a,x,y,xx,yy;
char f[50];
int cnt0;
int main()
{cinxy;cinxxyy;cina;for(int i1;ia;i){cinf[i];if(xxxf[i]S) { x-1;cnt;}if(xxxf[i]N) { x1;cnt;}if(yyyf[i]W) { y-1;cnt;}if(yyyf[i]E) { y1;cnt;}}if(x!xx||y!yy) cout-1;else coutcnt;
} 模拟 #includeiostream
#includecstring
#includecstdio
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,ans999999; //book用来标记一个点走没走过way储存了每一秒的风向。
int min(int x,int y)
{return xy?x:y;
}
int getnum(char c) //这个函数用来判断是东西南北里的哪一项。
{if(cN){return 0;}if(cE){return 1;}if(cS){return 2;}if(cW){return 3;}
}
void dfs(int x,int y,int now,int step) //step是现在几秒了now是步数。
{if(xendx yendy) //如果到达。{ansmin(ans,now); //更新答案return;}if(stepn1) //这里很重要不然会RE。{return;}int tx,ty,k;kway[step];txxnext[k][0];tyynext[k][1];if(tx1 txn ty1 tyn book[tx][ty]0) //如果这一秒风吹我走没有越界也没有来过这就代表可以走{book[tx][ty]1; //标记这儿我已走过了。dfs(tx,ty,now1,step1); //步数加一秒数加一book[tx][ty]0; //回溯}dfs(x,y,now,step1); //就是这一秒我不走。return;
}
int main()
{scanf(%d %d,startx,starty);scanf(%d %d,endx,endy);scanf(%d,n);for(i1;in;i){scanf(%c\n,t); way[i]getnum(t); //将每一秒的风向储存好。}dfs(startx,starty,0,1);if(ans999999) //如果ans还是999999就说明到不了。{puts(-1);}else{printf(%d,ans);}return 0;
} DFS 转载于:https://www.cnblogs.com/Roni-i/p/7650751.html
