题解 CF877D 【Olya and Energy Drinks】

durex_com · 2018-04-14 11:56:23 · 题解

题目大意：

有一个mad她房间脏乱差，因为其实她体质特殊，吸收了很多的化肥，所以说可以天涯咫尺，一次跑最多k距离。这个神犇的房间里有很多写着氮磷钾的袋子，不能通过，因为那是神圣之物。但是她想到一个神奇的小角落研究自己的珂学。。。已知这位dalao一开始躺在某个地方，求能不能研究珂学。。

bfs大法好。

枚举距离，剪枝看代码也能懂。 利用二进制存一个状态优化vis，就是从四个方向有没有到达过这个点；

没有任何的骚操作。

··· 贴代码吧。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<functional>
using namespace std;
int n,m,k;
struct zk
{
    int x,y;
}point,now;
int map[1001][1001];
int dis[1001][1001];
int vis[1001][1001];
int dir1[4]={1,0,-1,0};
int dir2[4]={0,1,0,-1};
int sta,stb;
int check(int x,int y)
{
    return x>=1&&x<=n&&y>=1&&y<=m;
}
int enx,eny;
void bfs(int a,int b)
{
    queue<zk> q;
    point.x=a;
    point.y=b;
    q.push(point);
    vis[a][b]=(1<<4)-1;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if (now.x==enx&&now.y==eny) return;
        for(int i=0;i<=3;i++)
        {
            for(int j=1;j<=k;j++)
            {
                point.x=now.x+dir1[i]*j;
                point.y=now.y+dir2[i]*j;
                if (map[point.x][point.y]) break;
                if (!check(point.x,point.y)) break;
                if (vis[point.x][point.y]&(1<<i)) break;
                int f=0;
                if (!vis[point.x][point.y]) f=1;
                vis[point.x][point.y]|=(1<<i);
                if (f)
                {
                    dis[point.x][point.y]=dis[now.x][now.y]+1;
                    q.push(point);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    char c;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin>>c;
        if (c=='#') map[i][j]=1;
    }
    scanf("%d%d%d%d",&sta,&stb,&enx,&eny);
    bfs(sta,stb);
    if (vis[enx][eny]) printf("%d",dis[enx][eny]);
    else printf("-1");
    return 0;
}