DLKKILL

DLKKILL's world

Codeforces Round #442 (Div. 2) - Olya and Energy Drinks (优化BFS)

题目链接:Olya and Energy Drinks

题目大意:

n*m 网格,每秒走1——k步

不能走‘#’

从指定位置走到目标位置所需的最短时间

题目分析:

优化BFS,记录所有点的步数。

当往某一方向走x<k布走到x点时该点已有步数小于现在步数,则不再在这一方向向下走,因为后面的点可以通过x点更快到达。

给出代码:

#include <iostream> 
#include <queue>  
#include <algorithm> 
#include <string> 
#include <vector>
using namespace std; 
const int maxn=1010; 
const int inf=0x3f3f3f3f;
struct node
{
int x;
int y;
int step;
};
vector<string> G;
int n,m,k;
int dis[maxn][maxn];
int vis[maxn][maxn];
int fx[4]={1,-1,0,0};
int fy[4]={0,0,1,-1};
int x1,y1,x2,y2;
int solve()
{
x1--;
y1--;
x2--;
y2--;
for(int i=0;i<maxn;i++)
{
for(int j=0;j<maxn;j++)
{
dis[i][j]=inf;
vis[i][j]=0;
}
}
node temp;
temp.x=x1;
temp.y=y1;
dis[x1][y1]=0;
temp.step=0;
queue<node> q;
q.push(temp);
    while(!q.empty())
{
node now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
for(int j=1;j<=k;j++)
{
node temp=now;
temp.x+=fx[i]*j;
temp.y+=fy[i]*j;
temp.step+=1;
if(temp.x<0||temp.x>=n||temp.y<0||temp.y>=m||G[temp.x][temp.y]=='#'||vis[temp.x][temp.y]&&dis[temp.x][temp.y]<temp.step)
break;
else
{
if(vis[temp.x][temp.y]==0&&dis[temp.x][temp.y]>temp.step)
{
dis[temp.x][temp.y]=temp.step;
vis[temp.x][temp.y]=1;
q.push(temp);
}
}
}
}
}
if(dis[x2][y2]==inf)
return -1;
else
return dis[x2][y2];
}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
G.push_back(s);
}
cin>>x1>>y1>>x2>>y2;
int t=solve();
cout<<t<<endl;
//system("pause");
return 0;
}


点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注