本文主要是介绍【洛谷】P3818 小A和uim之大逃离 II（bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1:思路：
vis前两维记录坐标，第三维记录是否用过药水，然后bfs即可，注意判重。
注意如果一个点用过了药水，则他所有可以扩展的点的状态都是喝过的，就是flag=1，不能再用药水了，不用再搜。
这个点没用过的话，它扩展的点的既有不用的（上下左右），也有用药水的，都要入队。
2:注意：
数据范围题目中是<=1000，开1010第二点会re，直接开2010，AC
3：ACcode:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2010;
struct node {int x,y,step,flag;
} cur,nxt;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
char mp[MAXN][MAXN];
bool v[MAXN][MAXN][2];
int n,m,f,d,r;
queue<node>q;
void bfs() {q.push({1,1,0,0});v[1][1][0] = true;while (!q.empty()) {cur = q.front();q.pop();if(cur.x==n&&cur.y==m) {cout<<cur.step<<"\n";return;}f=cur.flag;for (int i=0; i<4; ++i) {int xx = dx[i]+cur.x;int yy = dy[i]+cur.y;if (xx>0&&xx<=n&&yy>0&&yy<=m&&mp[xx][yy]!='#'&&!v[xx][yy][f]) {v[xx][yy][f] = true;q.push({xx,yy,cur.step+1,f});}}int xx = cur.x+d, yy = cur.y+r;if (f==0&&!v[xx][yy][1]&&xx>0&&xx<=n&&yy>0&&yy<=m&&mp[xx][yy]!='#') {v[xx][yy][1] = true;q.push({xx,yy,cur.step+1,1});}}cout<<-1<<"\n";
}
void solve() {cin>>n>>m>>d>>r;for (int i=1; i<=n; ++i)for (int j=1; j<=m; ++j)cin>>mp[i][j];bfs();
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t=1;
// cin>>t;while(t--) {solve();}return 0;
}over~
这篇关于【洛谷】P3818 小A和uim之大逃离 II（bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
