acwing板子
宽度优先遍历?
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
????int t = q.front();
????q.pop();
????for (int i = h[t]; i != -1; i = ne[i])
????{
????????int j = e[i];
????????if (!st[j])
????????{
????????????st[j] = true; // 表示点j已经被遍历过
????????????q.push(j);
????????}
????}
}
14572 走出迷宫
?
上道了上道了我上道了兄弟们！?
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef pair<int,int> PII;
int aa,bb,cc,dd;
int n,m;
char a[520][520];
int d[520][520];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int bfs()
{
queue<PII> q;
memset(d,-1,sizeof(d));
d[aa][bb]=0;
q.push({aa,bb});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=1&&x<=n&&y>=1&&y<=m&&d[x][y]==-1&&a[x][y]!='#')
{
d[x][y]=d[t.first][t.second]+1;
q.push({x,y});
}
}
}
return d[cc][dd];
}
int main()
{
//cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
while(cin>>n>>m){
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S') aa=i,bb=j;//起点位置
else if(a[i][j]=='E') cc=i,dd=j;//终点位置
}
}//cout<<aa<<" "<<bb<<" "<<cc<<" "<<dd<<endl;
if(bfs()==-1) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}?15136 迷宫
这题debug de了好久，给我整出来了哈哈哈哈哈
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
int n,m;
char a[520][520];
int d[520][520];
int aa,bb,cc,dd,ee,ff;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool flag=false;
int bfs()//纯路痴，从起点直接走到终点,不走障碍物和锁门的地方
{
queue<PII> q;
memset(d,-1,sizeof d);
d[aa][bb]=0;
q.push({aa,bb});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=2&&x<=n-1&&y>=2&&y<=m-1&&d[x][y]==-1&&a[x][y]!='W'&&a[x][y]!='D')//不能走有障碍物以及有锁门的地方
{
d[x][y]=d[t.first][t.second]+1;
q.push({x,y});
}
}
}
return d[cc][dd];
}
int bfs3()//聪明了，从起点先去拿个钥匙
{
queue<PII> q;
memset(d,-1,sizeof d);
d[aa][bb]=0;
q.push({aa,bb});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=2&&x<=n-1&&y>=2&&y<=m-1&&d[x][y]==-1&&a[x][y]!='W'&&a[x][y]!='D')//去拿钥匙的路上还是不能走锁门了的地方
{
d[x][y]=d[t.first][t.second]+1;
q.push({x,y});
}
}
}
return d[ee][ff];
}
int bfs2()//拿了钥匙直奔终点，从K到E
{
queue<PII> q;
memset(d,-1,sizeof d);
d[ee][ff]=0;
q.push({ee,ff});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=2&&x<=n-1&&y>=2&&y<=m-1&&d[x][y]==-1&&a[x][y]!='W')
{
d[x][y]=d[t.first][t.second]+1;
q.push({x,y});
}
}
}
return d[cc][dd];
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S') aa=i,bb=j;//起点位置
else if(a[i][j]=='E') cc=i,dd=j;//终点位置
else if(a[i][j]=='K') ee=i,ff=j;//钥匙的位置
}
}
/*if(bfs()==-1) cout<<"-1"<<endl;//直接被堵住了,有障碍物，打不通这个道路
else if(bfs()!=-1&&flag==false) cout<<bfs()<<endl;//直接从起点跑到了终点，没有被锁住的门直接走就行了,毋庸置疑这个绝对是最短路
else if(bfs()!=-1&&flag==true)//先去取钥匙，再去开门（开不开无所谓），碰到了就开，反正我有钥匙已经无敌了，啊这，万一拿不到钥匙
{
if(bfs3()==-1) cout<<bfs4()<<endl;//拿不到钥匙，找一条更远的路
cout<<bfs2()+bfs3()<<endl;//终于拿到钥匙了，随便找一条捷径过去就行了
}*/
//cout<<bfs()<<" "<<bfs2()<<" "<<bfs3<<endl;
if(bfs()==-1)//被堵住了要么就是有障碍物要么就是有门
{
if(bfs3()==-1)//钥匙拿不到，白瞎
cout<<"-1"<<endl;
else if(bfs2()==-1) //拿了钥匙也过不去，全是障碍物，更白瞎
cout<<"-1"<<endl;
else cout<<bfs2()+bfs3()<<endl;
}
else cout<<min(bfs2()+bfs3(),bfs())<<endl;
return 0;
}一晚上就做了两题（还是二星难度的.......）
唔~ 也挺棒了感觉嘻嘻嘻