Grid(bfs模板题)

题目大意是从左上角跳到右下角（如果能跳到）最少要多少步，其中每个格子都有一个数字代表跳的格数（必须按照这个格数跳），且每步不管跳多少格都算一步。

这道题直接套bfs的模板就可以AC了。

上代码：

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1000 + 5;
int m,n;
int ans;
char p[maxn][maxn];
bool vst[maxn][maxn];
int dir[4][2] = {0,1,0,-1,1,0,-1,0};
struct State{
int x,y;
int step;
}a[maxn];
bool check(State s){
if(!vst[s.x][s.y] && s.x >=0 && s.x < m && s.y >= 0 && s.y < n)
return 1;
else
return 0;
}
void bfs(State st){
queue<State> q;
State now,next;
st.step = 0;
q.push(st);
vst[st.x][st.y] = 1;
while(!q.empty()){
now = q.front();
if(now.x == m-1 && now.y == n-1){
ans = now.step;
return;
}
for(int i = 0;i < 4;i++){
next.x = now.x + dir[i][0]*(p[now.x][now.y] - '0');
next.y = now.y + dir[i][1]*(p[now.x][now.y] - '0');
next.step = now.step + 1;
if(check(next)){
q.push(next);
vst[next.x][next.y] = 1;
}
}
q.pop();
}
return;
}
int main()
{
while(cin>>m>>n){
int t = 0;
for(int i = 0;i < m;i++)
for(int j = 0;j < n;j++)
cin>>p[i][j];
bfs(a[0]);
if(ans == 0) cout<<"IMPOSSIBLE"<<endl;
else cout<<ans<<endl;
ans = 0;
}
return 0;
}

最后

以上就是激动帅哥为你收集整理的Grid(bfs模板题)的全部内容，希望文章能够帮你解决Grid(bfs模板题)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。