我这种优先队列的bfs能有几分啊?
查看原帖
我这种优先队列的bfs能有几分啊?
222341
twocats楼主2020/4/26 20:56
#include<bits/stdc++.h>
using namespace std;
const int N=500,inf=0x7FFFFFFF;
struct node{
	int x,y,t,u1,u2;
	friend bool operator<(node a,node b)
	{
		return a.t==b.t?( a.u1+a.u2==b.u1+b.u2?( a.u1>b.u1 ):( a.u1+a.u2 > b.u1+b.u2 ) ):( a.t>b.t );
	}
};
priority_queue<node> q;
int n,m,c1,c2,d,M[N][N],used[N][N][3];
int sx,sy,tx,ty,dt[12][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
void add(int x,int y,string s)
{
	M[x][y]=2;
	int num,b,e,t,z;
	for(int i=0;i<s.size();i++)	num=(num<<1)+(num<<3)+(s[i]^48);
	t=max(0,x-num+1),z=min(n-1,x+num-1),b=e=y;
	for(int i=t;i<=z;i++)
	{
		for(int j=b;j<=e;j++)	M[i][j]=max(M[i][j],1);
		b=max(0,b-1);
		e=min(m-1,e+1);
	}
}
void bfs()
{
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		if(t.x==tx&&t.y==ty)
		{
			printf("%d %d %d",t.t,t.u1,t.u2);
			return;
		}
		for(int i=0;i<12;i++)
		{
			node v;
			v.t=t.t+1;
			v.x=t.x+dt[i][0];
			v.y=t.y+dt[i][1];
			v.u1=t.u1+(M[v.x][v.y]==1?1:0);
			v.u2=t.u2+(i>7?1:0);
			if(M[v.x][v.y]==2||v.u1>c1||v.u2>c2||used[v.x][v.y][0]<v.t)	continue;
			if(used[v.x][v.y][0]==v.t)
			{
				if(used[v.x][v.y][1]+used[v.x][v.y][2]<v.u1+v.u2)	continue;
				if(used[v.x][v.y][1]+used[v.x][v.y][2]==v.u1+v.u2&&used[v.x][v.y][1]<=v.u1)	continue;
			}
			used[v.x][v.y][0]=v.t;
			used[v.x][v.y][1]=v.u1;
			used[v.x][v.y][2]=v.u2;
			q.push(v);
		}
	}
	puts("-1");
}
int main()
{
	freopen("bandit.in","r",stdin);
	freopen("bandit.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&m,&c1,&c2,&d);
	dt[8][0]=dt[10][1]=d;
	dt[9][0]=dt[11][1]=-d;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			string s;
			cin>>s;
			if(s[0]=='S')	sx=i,sy=j;
			if(s[0]=='T')	tx=i,ty=j;
			if(s[0]>'0'&&s[0]<='9')	add(i,j,s);
			used[i][j][0]=inf;
		}
	}
	q.push((node){sx,sy,0,0,0});
	bfs();
	return 0;
}
2020/4/26 20:56
加载中...