写完了DP的题解,来篇BFS的再说

作者居然刷出了一道紫题,也是有些懵逼

借鉴了楼上各位dalao的代码以后……

也磨出了一点代码

呈上:

#include<bits/stdc++.h>//万能头文件 
using namespace std;
struct Point//宽搜题先设个Point,这是作者的习惯 
{
    int x,y,step;
    bool key[11];
    int num;
};
int det[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
Point q[4000000],s;
bool used[11][11][2048];
int f,e;
int n,m,p,k,sk;
int g[11][11][11][11];
int kk[11][11][11];
int c(Point cur)//Point有用了 
{
	int res=0,tp=1;
	for(int i=1;i<=10;i++)
	{
		res=res+cur.key[i]*tp;
		tp=tp*2;
	}
	return res;
}
int main()
{
	cin>>n>>m>>p;
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		cin>>g[x1][y1][x2][y2];
		if(g[x1][y1][x2][y2]==0)g[x1][y1][x2][y2]=-1;
		g[x2][y2][x1][y1]=g[x1][y1][x2][y2];
	}
	cin>>sk;
	for(int i=1;i<=sk;i++)
	{
		int x1,y1,z1;
		cin>>x1>>y1>>z1;
		kk[x1][y1][z1]=1;
	}
	s.x=1,s.y=1,s.step=0;
	memset(s.key,0,sizeof(s.key));
	q[1]=s;
	f=e=1;
	while(f<=e)
	{
		Point u=q[f++];//Point又有用了 
		for(int i=0;i<4;i++)
		{
			Point v=u;//Point屡试不爽 
			v.x=u.x+det[i][0],v.y=u.y+det[i][1],v.step=u.step+1;
			if(v.x<1||v.x>n||v.y<1||v.y>m)continue;
			if(g[u.x][u.y][v.x][v.y]==-1)continue;
			if(g[u.x][u.y][v.x][v.y]>0&&u.key[g[u.x][u.y][v.x][v.y]]==0)continue;
			if(v.x==n&&v.y==m)
			{
				cout<<v.step<<endl;
				return 0;
			}
			
			//if(kk[v.x][v.y]!=0)v.key[kk[v.x][v.y]]=1;  坎坷之路啊! 
			for(int i=1;i<=10;i++)
			if(kk[v.x][v.y][i]==1) v.key[i]=1;
			v.num=c(v);
			if(used[v.x][v.y][v.num]==1)continue;
			q[++e]=v;
			used[v.x][v.y][v.num]=1;
			
		}
	}
	cout<<-1<<endl;
	return 0;
}

希望对各位有帮助!!!