问题 D: 迷宫
注意行列的坑点即可，可以多开一维来判断方向
优先枚举转向少的，因为转向越少越可能达到
点击查看代码
int vis[110][110][5];//第三表示方向 0向上 1向右 2向下 3向左
char st[110][110];//存图，注意坑点：行列反过来
struct node{
int x,y,kt,op;
bool operator<(const node &v)const{//优先级
return kt>v.kt;
}
};
int n,m,x1,x2,yy1,y2,k;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void bfs(){
priority_queue<node> q;
//枚举四个方向
q.push({x1,yy1,0,0});
q.push({x1,yy1,0,1});
q.push({x1,yy1,0,2});
q.push({x1,yy1,0,3});
while(q.size()){
node t=q.top();
if(t.x==x2&&t.y==y2&&t.kt<=k){
cout<<"yes\n";
return;
}
q.pop();
if(vis[t.x][t.y][t.op]||t.kt>k) continue;//同一个方向走过或者已经超过k转了直接跳过
vis[t.x][t.y][t.op]=1;
//枚举四个方向
for(int i=0;i<4;i++){
int x=t.x+dx[i],y=t.y+dy[i];
if(x<1||x>n||y<1||y>m||st[x][y]=='*') continue;
if(t.op!=i){//如果方向不同，要多走一步
q.push({x,y,t.kt+1,i});
}
else q.push({x,y,t.kt,i});
}
}
cout<<"no\n";
return;
}
问题 E: 水陆距离
多源bfs
判断每一个点距离0的最近距离
对于只有一个0点，可以利用队列遍历每个点，但是对于多个0点，我们可以利用优先队列维护最小值，优先使用最小的点，这样它遍历的附近点一定是最小的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int g[1010][1010],vis[1010][1010];
int a[1010][1010];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
struct node{
int x,y,step;
bool operator<(const node &v)const{
return step>v.step;
}
};
priority_queue<node> q;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(!g[i][j]) q.push({i,j,0});
}
}
while(q.size()){
node t=q.top();
q.pop();
if(vis[t.x][t.y]) continue;
a[t.x][t.y]=t.step;
vis[t.x][t.y]=1;
for(int i=0;i<4;i++){
int x=t.x+dx[i],y=t.y+dy[i];
if(vis[x][y]||x<1||x>n||y<1||y>m) continue;
q.push({x,y,t.step+1});
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<' ';
}
cout<<'\n';
}
return 0;
}