三个点,让我挂了75分
  • 板块学术版
  • 楼主唐一文
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/10/16 18:04
  • 上次更新2023/11/4 03:36:35
查看原帖
三个点,让我挂了75分
150843
唐一文楼主2021/10/16 18:04

RT,求调今天2D/kel

先去吃饭了,可能会回复得比较迟

#include<bits/stdc++.h>
#define il inline
#define re register
#define iL (1<<20)
#define TEM template<class T>il void
#define flush() fwrite(Out,1,iter-Out,stdout),iter=Out
#define gc() ((iS==iT)?(iT=(iS=ibuf)+fread(ibuf,1,iL,stdin),(iS==iT)?EOF:*iS++):*iS++)
using namespace std;
namespace IO{
	char ibuf[iL],*iS=ibuf+iL,*iT=ibuf+iL,Out[iL],*iter=Out;
	TEM Read(re T &x){re char c;for(c=getchar();!isdigit(c);c=getchar());for(x=0;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());}
	TEM write(re T x){re T c[35],l;for(l=0;!l||x;c[l++]=x%10,x/=10);for(;l;*iter++=c[--l]+'0');flush();}
}
using namespace IO;
#define MAXN 2005
struct Node{int x,y,dir,dis;il bool operator<(const Node&tmp)const{return dis>tmp.dis;}};
priority_queue<Node>Q;
int n,m,A,B,C,D,f[MAXN][MAXN][4];char s[MAXN][MAXN];bool vis[MAXN][MAXN][4];
il bool Check(int x,int y){return x>0&&x<=n&&y>0&&y<=m&&s[x][y]!='#';}
il void Ins(int nx,int ny,int ndir,int val){if(Check(nx,ny)&&f[nx][ny][ndir]>val)Q.push(Node{nx,ny,ndir,f[nx][ny][ndir]=val});}
int main(){
	Read(n),Read(m),Read(A),Read(B),Read(C),Read(D);
	for(re int i=1;i<=n;++i)scanf("%s",s[i]+1);
	memset(f,0x3f,sizeof(f));
	for(re int i=1;i<=n;++i)for(re int j=1;j<=m;++j)if(s[i][j]=='S')Ins(i,j-1,0,0),Ins(i,j+1,1,0),Ins(i-1,j,2,0),Ins(i+1,j,3,0);
	for(re int x,y,dir,dis;!Q.empty();){
		x=Q.top().x,y=Q.top().y,dir=Q.top().dir,dis=Q.top().dis,Q.pop();
		if(s[x][y]=='E'){write(dis);return 0;}
		if(vis[x][y][dir])continue;vis[x][y][dir]=true;
		if(s[x][y]=='|'){
			if(dir<2)Ins(x-1,y,2,dis+A),Ins(x+1,y,3,dis+A);
			if(dir==2)Ins(x-1,y,2,dis+A);if(dir==3)Ins(x+1,y,3,dis+A);
		}
		if(s[x][y]=='-'){
			if(dir>1)Ins(x,y-1,0,dis+A),Ins(x,y+1,1,dis+A);
			if(dir==0)Ins(x,y-1,0,dis+A);if(dir==1)Ins(x,y+1,1,dis+A);
		}
		if(s[x][y]=='/'){
			if(dir==0)Ins(x+1,y,3,dis+B);if(dir==1)Ins(x-1,y,2,dis+B);
			if(dir==2)Ins(x,y+1,1,dis+B);if(dir==3)Ins(x,y-1,0,dis+B);
		}
		if(s[x][y]=='\\'){
			if(dir==0)Ins(x-1,y,2,dis+B);if(dir==1)Ins(x+1,y,3,dis+B);
			if(dir==2)Ins(x,y-1,0,dis+B);if(dir==3)Ins(x,y+1,1,dis+B);
		}
		if(s[x][y]=='.'){
			if(dir==0)Ins(x-1,y,2,dis+C),Ins(x+1,y,3,dis+C),Ins(x,y-1,0,dis+C);
			if(dir==1)Ins(x-1,y,2,dis+C),Ins(x+1,y,3,dis+C),Ins(x,y+1,1,dis+C);
			if(dir==2)Ins(x,y-1,0,dis+C),Ins(x,y+1,1,dis+C),Ins(x+1,y,3,dis+C);
			if(dir==3)Ins(x,y-1,0,dis+C),Ins(x,y+1,1,dis+C),Ins(x-1,y,2,dis+C);
		}
		if(s[x][y]=='<'){if(dir==0)Ins(x,y-2,0,dis);if(dir>1)Ins(x,y-1,0,dis+D);}
		if(s[x][y]=='>'){if(dir==1)Ins(x,y+2,1,dis);if(dir>1)Ins(x,y+1,1,dis+D);}
		if(s[x][y]=='^'){if(dir<2)Ins(x-1,y,2,dis+D);if(dir==2)Ins(x-2,y,2,dis);}
		if(s[x][y]=='v'){if(dir<2)Ins(x+1,y,3,dis+D);if(dir==3)Ins(x+2,y,3,dis);}
	}
	printf("-1");
}
2021/10/16 18:04
加载中...