0-1BFS教程
E - Stronger Takahashi
题意
给定一个\(H\times W\)的棋盘，从\((1,1)\)点走到\((H,W)\)点，\(.\)是可以直接通过的位置或者通过使用一次能力，使得前方\(2\times 2\)的障碍消除，问走到终点最少需要使用几次能力。
思路
由于我们只需要考虑能力使用的次数，我们可以将直接走到的格子花费设置为\(0\)，而需要使用能力通过的地方需要花费\(1\)，于是问题就转化成了\(0-1BFS\)问题，总时间复杂度就是\(O(HW)\)。
参考代码
点此展开
#include <bits/stdc++.h>
using namespace std;
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define din(x) scanf("%lf",&x)
#define mp make_pair
#define pb push_back
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int N=510;
char g[N][N];
bool st[N][N];
int dist[N][N];
int ndx[]={0,0,1,-1},ndy[]={1,-1,0,0};//上下左右
//使用一次能力后能够到达的点
int dx[]={0,0,0,0,1,1,1,1,1,2,2,2,-1,-1,-1,-1,-1,-2,-2,-2};
int dy[]={1,2,-1,-2,-2,-1,0,1,2,-1,0,1,-2,-1,0,1,2,-1,0,1};
int main()
{
int n,m;
in(n),in(m);
for(int i=1;i<=n;i++)
cin>>g[i]+1;
deque<pii> q;
memset(dist,0x3f,sizeof dist);
dist[1][1]=0;
q.push_back(mp(1,1));
while(!q.empty())
{
auto tmp=q.front();
q.pop_front();
int x=tmp.first,y=tmp.second;
if(st[x][y]) continue;
st[x][y]=true;
//先查看上下左右的点能不能松弛
for(int i=0;i<4;i++)
{
int nx=x+ndx[i],ny=y+ndy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&dist[nx][ny]>dist[x][y]&&g[nx][ny]=='.')
{
dist[nx][ny]=dist[x][y];
q.push_front(mp(nx,ny));
}
}
//检查使用能力后能不能松弛附近的点
for(int i=0;i<20;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>0&&nx<=n&&ny>0&&ny<=m)
{
if(dist[nx][ny]>dist[x][y]+1)
{
dist[nx][ny]=dist[x][y]+1;
q.push_back(mp(nx,ny));
}
}
}
}
cout<<dist[n][m]<<endl;
return 0;
}
D - Wizard in Maze
思路
与上一题类似，只需要注意使用能力后能访问那些点即可
参考代码
点此展开
#include <bits/stdc++.h>
using namespace std;
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define din(x) scanf("%lf",&x)
#define mp make_pair
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int N=1e3+10;
const int mod=1e9+7;
char g[N][N];
int dist[N][N];
bool st[N][N];
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
int ndx[]={-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
int ndy[]={-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
int main()
{
int n,m;
in(n),in(m);
int sx,sy,ex,ey;
in(sx),in(sy),in(ex),in(ey);
for(int i=1;i<=n;i++)
cin>>g[i]+1;
memset(dist,0x3f,sizeof dist);
dist[sx][sy]=0;
deque<pii> q;
q.push_front(mp(sx,sy));
while(!q.empty())
{
auto tmp=q.front();
q.pop_front();
int x=tmp.first,y=tmp.second;
if(st[x][y]) continue;
st[x][y]=true;
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>0&&nx<=n&&ny>0&&ny<=m&&dist[nx][ny]>dist[x][y]&&g[nx][ny]=='.')
{
dist[nx][ny]=dist[x][y];
q.push_front(mp(nx,ny));
}
}
for(int i=0;i<24;i++)
{
int nx=x+ndx[i],ny=y+ndy[i];
if(nx>0&&nx<=n&&ny>0&&ny<=m&&g[nx][ny]=='.')//注意这里是走到附近是.的位置
{
if(dist[nx][ny]>dist[x][y]+1)
{
dist[nx][ny]=dist[x][y]+1;
q.push_back(mp(nx,ny));
}
}
}
}
if(dist[ex][ey]==0x3f3f3f3f)
dist[ex][ey]=-1;//如果无法到达就输出-1
cout<<dist[ex][ey];
return 0;
}