写完了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;
}