求助
查看原帖
求助
421517
棠棠棠棠棠এ楼主2021/12/29 19:21
#include<bits/stdc++.h>
using namespace std;
const int ll=(1<<30)+100;
char mp[2010][2010];
bool sf[2010][2010][4];
int n,m,a,b,c,d;
struct node{int x,y,la,ti;}now;
queue<node> q;
int bfs()
{
	int ans=ll;
	while(!q.empty())
	{
		now=q.front(),q.pop();
		if(now.x<0||now.y<0||now.x>=n||now.y>=m) continue;
		if(sf[now.x][now.y][now.la]) continue;
		else sf[now.x][now.y][now.la]=true;	
		if(mp[now.x][now.y]=='#') sf[now.x][now.y][0]=sf[now.x][now.y][1]=sf[now.x][now.y][2]=sf[now.x][now.y][3]=true;
		if((mp[now.x][now.y]=='^'&&now.la==0)||(mp[now.x][now.y]=='v'&&now.la==1)||(mp[now.x][now.y]=='<'&&now.la==2)||(mp[now.x][now.y]=='>'&&now.la==3)) continue;
		if(now.ti>=ans) continue;
		if(mp[now.x][now.y]=='E')
		{
			ans=now.ti;
			continue;
		}
		if(mp[now.x][now.y]=='S'||mp[now.x][now.y]=='.')
		{
			if(mp[now.x][now.y]=='S') sf[now.x][now.y][0]=sf[now.x][now.y][1]=sf[now.x][now.y][2]=sf[now.x][now.y][3]=true;
			else now.ti+=c;
			++now.x,now.la=0,q.push(now),--now.x;
			--now.x,now.la=1,q.push(now),++now.x;
			++now.y,now.la=2,q.push(now),--now.y;
			--now.y,now.la=3,q.push(now),++now.y;
			continue;
		}
		if(mp[now.x][now.y]=='|')
		{
			now.ti+=a;
			if(now.la==0) ++now.x,q.push(now);
			else if(now.la==1) --now.x,q.push(now);
			else ++now.x,now.la=0,q.push(now),--now.x,--now.x,now.la=1,q.push(now);
			continue;
		}
		if(mp[now.x][now.y]=='-')
		{
			now.ti+=a;
			if(now.la==2) ++now.y,q.push(now);
			else if(now.la==3) --now.y,q.push(now);
			else ++now.y,now.la=2,q.push(now),--now.y,--now.y,now.la=3,q.push(now);
			continue;
		}
		if(mp[now.x][now.y]=='/')
		{
			now.ti+=b;
			if(now.la==0) now.la=3,--now.y;
			else if(now.la==1) now.la=2,++now.y;
			else if(now.la==2) now.la=1,--now.x;
			else now.la=0,++now.x;
			q.push(now);
			continue;
		}
		if(mp[now.x][now.y]=='\\')
		{
			now.ti+=b;
			if(now.la==1) now.la=3,--now.y;
			else if(now.la==0) now.la=2,++now.y;
			else if(now.la==3) now.la=1,--now.x;
			else now.la=0,++now.x;
			q.push(now);
			continue;
		}
		if(mp[now.x][now.y]=='^')
		{
			if(now.la==1) now.x-=2;
			else now.la=1,--now.x,now.ti+=d;
			q.push(now);
			continue;
		}
		if(mp[now.x][now.y]=='v')
		{
			if(now.la==0) now.x+=2;
			else now.la=0,++now.x,now.ti+=d;
			q.push(now);
			continue;
		}
		if(mp[now.x][now.y]=='<')
		{
			if(now.la==3) now.y-=2;
			else now.la=3,--now.x,now.ti+=d;
			q.push(now);
			continue;
		}
		if(mp[now.x][now.y]=='>')
		{
			if(now.la==2) now.y+=2;
			else now.la=2,++now.y,now.ti+=d;
			q.push(now);
			continue;
		}
	}
	return ans;
}
int main()
{
	scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
	for(int i=0;i<n;++i)
	{
		scanf("%s",mp[i]);
		for(int j=0;j<m;++j)
			if(mp[i][j]=='S') now.x=i,now.y=j,now.la=0,now.ti=0,q.push(now);
	}
	int ans=bfs();
	if(ans==ll) cout<<-1;
	else cout<<ans;
	return 0;
}

结果

2021/12/29 19:21
加载中...