第五题 sirius

阚原
2023-12-01

森林里有一头狼,它在树林了觅食。突然,它发现了一头羚羊,羚羊也发现了它,转身便跑。狼很有经验,它没有茫然地去追这头鹿,因为,它知道,鹿会在没有动物抓它是在x单位的时间内怎么走,而林子里的路纵横交错,许多地方都有路障,我们可以把林子变成一个n*m的矩形,有n行,m列。狼的位置用字符’x’来表示,羚羊的位置用字符’y’来表示,通路用字符’.‘来表示,路障用字符’#'来表示。狼每一单位时间,最多走2格,每一单位时间都不可以与羚羊在同一格,不然就要被羚羊发现了。狼要在羚羊之前来到某地,停止奔跑,进行等待。狼想要知道抓住羚羊的最快的路该怎么走,但它不会算,可是它有一台高科技的笔记本电脑,里面有c++,但是它不会编,于是就请聪明的你,打开c++,编写这个程序吧!

第五题 sirius

你可以稳妥地用贪心大法拿到20分。贪分大法!!!

#include <bits/stdc++.h>
using namespace std;
int main(){
	cout<<"No";
	return 0;
}

此题为wolf的升级版,走0步=向一个方向走一步,再走回来。所以走0步,可以不考虑,只要考虑走一步和走两步。

没有太多的技术含量

代码走起:

#include <bits/stdc++.h>
using namespace std;
int a[55][110][110],mp[110][110],sx,sy,ex,ey,o[55][110][110];
deque<int>q1;
deque<int>q2;
deque<int>ti;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main(){
	memset(mp,-1,sizeof(mp));
	int b,n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char ch;
			cin>>ch;
			if(ch!='#')mp[i][j]=0;
			if(ch=='y')sx=i,sy=j;
			if(ch=='x')ex=i,ey=j;
		}
	}
	cin>>b;
	for(int i=1;i<=b;i++){
		char ch;
		cin>>ch;
		switch(ch){
			case 'u':sx--;break;
			case 'd':sx++;break;
			case 'l':sy--;break;
			case 'r':sy++;break;
		}
		a[i][sx][sy]=1;
	}
	q1.push_back(ex);
	q2.push_back(ey);
	ti.push_back(0);
	while(!ti.empty()){
		if(ti.front()>=b){
			cout<<"No";
			return 0;
		}
		int x=q1.front(),y=q2.front();
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[ti.front()+1][nx][ny]==0&&o[ti.front()+1][nx][ny]==0&&mp[nx][ny]==0){
				o[ti.front()+1][nx][ny]=1;
				q1.push_back(nx);
				q2.push_back(ny);
				ti.push_back(ti.front()+1);
				for(int k=ti.front()+2;k<=b;k++){
					if(a[k][nx][ny]==1){
						cout<<"Yes "<<ti.front()+1;
						return 0;
					}
				}
			}
		}
		for(int i=0;i<4;i++){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[ti.front()+1][tx][ty]==0&&mp[tx][ty]==0){
				for(int j=0;j<4;j++){
					int nx=tx+dx[j],ny=ty+dy[j];
					if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[ti.front()+1][nx][ny]==0&&o[ti.front()+1][nx][ny]==0&&mp[tx][ty]==0){
						o[ti.front()+1][nx][ny]=1;
						q1.push_back(nx);
						q2.push_back(ny);
						ti.push_back(ti.front()+1);
						for(int k=ti.front()+2;k<=b;k++){
							if(a[k][nx][ny]==1){
								cout<<"Yes "<<ti.front()+1;
								return 0;
							}
						}
					}
				}
			}
		}
		q1.pop_front();
		q2.pop_front();
		ti.pop_front();
	}cout<<"No";
	return 0;
}
 类似资料: