D. Olya and Energy Drinks

Codeforces Round #442 (Div. 2)

题目链接:https://codeforces.com/contest/877/problem/D

题目描述:

tm

思路:

题目大意是,有一个n*m的地图,由"#"(不可走)和"."(可走)组成。获得起点(x1,y1)和终点(x2,y2)的位置。每次可以走1~k步。每走一次用时一秒。问从起点到达终点最少用时多久。输出从起点到达终点所用的时间,如果不能到达终点输出-1.
利用BFS,要注意的是因为有一个速度K步/S,所以每一次可以走1~k步,所用的时间都是1秒。

代码:

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;

int n,m,k;
char a[1005][1005];
int vis[1005][1005];           //记录地图中走过的点
int dir[4][2]={0,1,1,0,0,-1,-1,0};    //只能向上、下、左、右四个方向移动
int x1,x2,y1,y2;
struct node{
    int x,y,s;     //s记录所用的时间
}st;

int bfs(){
    if(x1==x2&&y1==y2){
        return 0;
    }
    queue<node>q;
    q.push(st);
    node nx;           //nx为下一步的位置
    vis[st.x][st.y]=1;
    while(!q.empty()){
        node now;
        now=q.front();    //now为当前位置
        q.pop();
        for(int i=0;i<4;i++){
            for(int j=1;j<=k;j++){
                nx.x=now.x+dir[i][0]*j;     
                nx.y=now.y+dir[i][1]*j;
                if(nx.x==x2&&nx.y==y2){
                    return now.s+1;
                }
                if(nx.x<=0||nx.y<=0||nx.x>n||nx.y>m||a[nx.x][nx.y]=='#'){
                    break;
                }
                if(vis[nx.x][nx.y]==0){
                    vis[nx.x][nx.y]=1;
                    nx.s=now.s+1;
                    q.push(nx);
                }
            }
        }
    }
    return -1;
}

int main(){
    #ifdef HH
    freopen("G:/in.txt","r",stdin);
    #endif // HH
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
    }
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    st.x=x1;
    st.y=y1;
    st.s=0;
    printf("%d\n",bfs());
    return 0;
}
Last modification:January 31st, 2020 at 09:54 pm
如果觉得我的文章对你有用,请随意赞赏