Gym - 101617D_Jumping Haybales（BFS）

Sample Input

4 2

.###

#...

.#..

#.#.

3 1

.#.

.#.

.#.

Sample Output

4

-1

题意：给一个n*n的图，每次最多能跳k个格子，只能向南（下）或东（右）跳，不能落在‘#’上，求从右上角到左下角的最短时间。

题解：看到图、最短时间第一个反应就是BFS，可惜超时，候来优化了几次，勉强卡时间过了，别人貌似有DP过的，以后抽时间补上这种方法。

先说BFS吧，假设点为（i，j）那么标记的时候会把(i+1,j)，(i+2,j)...(i+k,j)，(i,j+1)，(i,j+2)...(i,j+k)标记，而接下来会走如果(i+1,j)，则会标记(i+2,j)，(i+3,j)...(i+k+1,j)，这样会有重复标记，导致时间复杂度上升。

通过观察不难发现，每次新标记的都是后面几个，所以我们可以倒着标记，当发现这个点被标记时就结束就好。

不过这样需要考虑方向问题，即是横向走的时候被标记了，还是纵向走的时候被标记了，具体看代码。

//如果标记过就结束循环

1111

1000

1111

1111

//就会出现类似这样的情况，原因是第三行横向标记过，导致二三四列在标记的时候碰到第三行就停止了。

//只是举个例子，这不是代码实际标记情况。

附上代码

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

const int maxn = 2050;

struct node

{

    int x,y,step;

};

int f[maxn][maxn],n,k;

char s[maxn][maxn];

void BFS()

{

    int i,MIN,dx,dy,m;

    queue<node> q;

    node t1,t2;

    memset(f,0,sizeof(f));

    //关于标记，1 代表从上方跳过来，2 代表从左边跳过来，3代表上方，左边都到过这个点。

    f[0][0] = 3;

    t1.x = t1.y = t1.step = 0;

    q.push(t1);

    MIN = -1;

    while(!q.empty())

    {

        t1 = q.front();

        q.pop();

        if(t1.x==n-1&&t1.y==n-1)//结束标志

        {

            MIN = t1.step;

            break;

        }

        //纵向标记。

        if(t1.x+k>=n)//如果最长距离跳出了边界，那么把距离控制在边界内。

            m = n - t1.x - 1;

        else

            m = k;

        for(i=m;i>=1;i--)

        {

            dx = t1.x + i;

            dy = t1.y;

            if(f[dx][dy]==1||f[dx][dy]==3)

                break;

            if(s[dx][dy]!='#')

            {

                if(!f[dx][dy])

                    f[dx][dy] = 1;

                else

                    f[dx][dy] = 3;

                t2.x = dx;

                t2.y = dy;

                t2.step = t1.step + 1;

                q.push(t2);

            }

        }

        //横向标记

        if(t1.y+k>=n)

            m = n - t1.y - 1;

        else

            m = k;

        for(i=m;i>=1;i--)

        {

            dx = t1.x;

            dy = t1.y + i;

            if(f[dx][dy]==2||f[dx][dy]==3)

                break;

            if(s[dx][dy]!='#')

            {

                if(!f[dx][dy])

                    f[dx][dy] = 2;

                else

                    f[dx][dy] = 3;

                t2.x = dx;

                t2.y = dy;

                t2.step = t1.step + 1;

                q.push(t2);

            }

        }

    }

    printf("%d\n",MIN);

}

int main()

{

    int i;

    scanf("%d%d",&n,&k);

    for(i=0;i<n;i++)

        scanf("%s",s[i]);

    BFS();

    return 0;

}

巴特西

Gym - 101617D_Jumping Haybales（BFS）

Sample Input

Sample Output

最新文章

热门文章