【BZOJ1632】[Usaco2007 Feb]Lilypad Pond

描述 Description

Farmer John 建造了一个美丽的池塘，用于让他的牛们审美和锻炼。这个长方形的池子被分割成了 M 行和 N 列 (1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30) 正方形格子的 。某些格子上有惊人的坚固的莲花，还有一些岩石，其余的只是美丽，纯净，湛蓝的水。 贝茜正在练习芭蕾舞，她从一个莲花跳跃到另一个莲花，当前位于一个莲花。她希望在莲花上一个一个的跳，目标是另一个给定莲花。她能跳既不入水，也不到一个岩石上。 令门外汉惊讶的是，贝茜的每次的跳跃像中国象棋的马一样：横向移动 1，纵向移动 2，或纵向移动 1，横向移动 2。贝茜有时可能会有多达 8 个选择的跳跃。 Farmer John 在观察贝茜的芭蕾舞联系，他意识到有时候贝茜有可能跳不到她想去的目的地，因为路上有些地方没有莲花。于是他想要添加几个莲花使贝茜能够完成任务。一贯节俭的 Farmer John 想添加最少数量的莲花。当然，莲花不能放在石头上。 请帮助 Farmer John 确定必须要添加的莲花的最少数量。在添加的莲花最少基础上，算出贝茜从起始点跳到目标点需要的最少的步数。最后，还要算出满足添加的莲花的最少数量时，跳跃最少步数的跳跃路径的条数。

输入格式 InputFormat

第 1 行: 两个整数 M , N.

第 2..M + 1 行: 第 i + 1 行，第 i + 1 行 有 N 个整数，表示该位置的状态: 0 为水; 1 为莲花; 2 为岩石; 3 为贝茜开始的位置; 4 为贝茜要去的目标位置.

输出格式 OutputFormat

第 1 行: 一个整数: 需要添加的最少的莲花数. 如果无论如何贝茜也无法跳到，输出 -1.

第 2 行: 一个整数: 在添加的莲花最少基础上，贝茜从起始点跳到目标点需要的最少的步数。如果第 1 行输出 - 1，这行不输出。 第 3 行: 一个整数: 添加的莲花的最少数量时，跳跃步数为第 2 行输出的值的跳跃路径的条数 如果第 1 行输出 - 1，这行不输出。

样例输入 SampleInput

30 30
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2
0 0 0 0 0 0 0 2 0 2 2 0 0 2 0 2 0 2 2 0 0 2 0 0 2 0 2 0 0 2
2 0 2 0 0 0 0 0 0 2 2 0 2 2 2 0 2 2 0 0 2 0 2 0 2 2 0 0 0 0
2 0 4 0 0 0 0 2 0 0 0 0 0 2 0 2 0 0 0 1 0 2 0 0 0 0 2 0 2 2
2 0 2 0 2 2 0 0 1 2 2 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 2 2 2 2 0 0 2 0 2 2 0 2 2 0 2 0 2 0 0 0 0 0 0 0

样例输出 SampleOutput

83
85
9706761917300736

来源 Source

Silver

BZOJ 1632

代码 Code

广搜实现 DP(?) 要用到 long long。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff
const int dx[9]={0,-2,-1,1,2,2,1,-1,-2};
const int dy[9]={0,1,2,2,1,-1,-2,-2,-1};
struct point
{
    long long z;
    int y,x;//x=Lilypad;y=skip;z=path;
}f[305][305];
struct que
{
    int x,y;
}q[90000];
int a[305][305];
bool b[305][305];
int i,j,t,n,m,l,r,k,sx,sy,ex,ey;
void bfs()
{
    int i,j,t,tx,ty;
    memset(b,0,sizeof(b));
    l=0;r=l;
    q[l].x=sx;q[l].y=sy;
    f[sx][sy].x=0;f[sx][sy].y=0;f[sx][sy].z=1;
    b[sx][sy]=true;
    while (r>=l)
    {
        for (i=1;i<=8;i++)
        {
            tx=q[l].x+dx[i];ty=q[l].y+dy[i];
            if (tx<=0 || ty<=0 || tx>m || ty>n || a[tx][ty]==2) continue;
            t=(a[tx][ty]==0)?1:0;
            if (f[tx][ty].x>f[q[l].x][q[l].y].x+t)
            {
                f[tx][ty].x=f[q[l].x][q[l].y].x+t;
                f[tx][ty].y=f[q[l].x][q[l].y].y+1;
                f[tx][ty].z=f[q[l].x][q[l].y].z;
                if (b[tx][ty]==false) 
                {
                    q[++r].x=tx;q[r].y=ty;
                    b[tx][ty]=true;
                }
                continue;
            }
            if (f[tx][ty].x==f[q[l].x][q[l].y].x+t && f[tx][ty].y>f[q[l].x][q[l].y].y+1)
            {
                f[tx][ty].y=f[q[l].x][q[l].y].y+1;
                f[tx][ty].z=f[q[l].x][q[l].y].z;
                if (b[tx][ty]==false) 
                {
                    q[++r].x=tx;q[r].y=ty;
                    b[tx][ty]=true;
                }
                continue;
            }
            if (f[tx][ty].x==f[q[l].x][q[l].y].x+t && f[tx][ty].y==f[q[l].x][q[l].y].y+1)
            {
                f[tx][ty].z+=f[q[l].x][q[l].y].z;
                if (b[tx][ty]==false) 
                {
                    q[++r].x=tx;q[r].y=ty;
                    b[tx][ty]=true;
                }
                continue;
            }
        }
        b[q[l].x][q[l].y]=false;
        l++;
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    for (i=1;i<=m;i++) for (j=1;j<=n;j++)
    {
        f[i][j].x=f[i][j].y=inf;
        f[i][j].z=0;
        scanf("%d",&a[i][j]);
        if (a[i][j]==3) {sx=i;sy=j;}
        if (a[i][j]==4) {ex=i;ey=j;}
    }
    bfs();
    if (f[ex][ey].x==inf) printf("-1n");
    else 
    {
        printf("%dn%dn%lldn",f[ex][ey].x,f[ex][ey].y,f[ex][ey].z);
    }
    return 0;
}