题目

思路

一眼bfs
好像需要记录的东西有点多啊，那就交给数组吧
$s{t}_{ij0/1}$表示用/没用特殊步走到(i,j)的步数，然后套bfs模板即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,d,r,st[N][N][2];
char s[N][N];
struct Point{int x,y,u;
};
queue<Point> Q;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool check(int x,int y) { return x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]=='.'; }
int main()
{cin>>n>>m>>d>>r;for(int i=1;i<=n;i++) cin>>s[i]+1;memset(st,-1,sizeof(st));//没有到达的状态初始-1st[1][1][0]=0;Q.push({1,1,0});while(!Q.empty()&&st[n][m][0]==-1&&st[n][m][1]==-1){Point now=Q.front();Q.pop();for(int i=0;i<4;i++){int x=now.x+dx[i],y=now.y+dy[i];if(check(x,y)&&st[x][y][now.u]==-1){Q.push({x,y,now.u});st[x][y][now.u]=st[now.x][now.y][now.u]+1;if(!now.u&&check(x+d,y+r)&&st[x+d][y+r][1]==-1){Q.push({x+d,y+r,1});st[x+d][y+r][1]=st[x][y][0]+1;}}}}if(st[n][m][0]==-1&&st[n][m][1]==-1) cout<<-1;else cout<<min(st[n][m][0]==-1?1<<30:st[n][m][0],st[n][m][1]==-1?1<<30:st[n][m][1]);return 0;
}

end

完结撒花