[JZOJ 4855]荷花池塘

Description

于大夫建造了一个美丽的池塘，用来让自己愉快的玩耍。这个长方形的池子被分割成了M 行 和N 列的正方形格子。池塘中有些地方是可以跳上的荷叶，有些地方是不能放置荷叶也不 能跳上的岩石，其他地方是池水（当然于大夫也是不能游泳的）。于大夫十分有趣，他在池 塘跳跃的方式和象棋中的马一样可以向八个方向走日字形，而且于大夫只能跳上荷叶。于大 夫每天从一个给定的有荷叶的地方出发，试图到达另一个给定的有荷叶的地方。但有一天他 发现自己无论如何也不能到达目的地了，除非再在水中放置几个荷叶。于大夫想让你告诉他， 最少还需放置几片荷叶？在放置荷叶最少的前提下，最少需要几步能到达目的地？

Input

第1 行: 两个整数M , N 第2…M+1 行:第i + 1 行有N 个整数，表示该位置的状态: 0 为水; 1 为荷叶; 2 为 岩石; 3 为于大夫开始的位置; 4 为于大夫要去的目标位置.

Output

一行两个整数空格隔开：分别为最少放置荷叶数和最小放置为前提下最少步数。（,如果无 论如何也不能到达请输出-1 -1）。

Sample Input

4 8 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 4 0 0 3 0 0 0 0 0 1 0

Sample Output

2 6

Data Constraint

10%的数据n，m<=4 30%的数据n，m<=10 50%的数据n，m<=30 70%的数据n，m<=50 100%的数据n，m<=100

The Solution

简单的bfs题目 就是要你在跳跃荷叶最少的情况下求最短路。 我们可以设一个f[i][j]表示为到达(i,j)所需的最少荷叶数量 一个 g[i][j]表示在到达(i,,j)所需的最少荷叶数量的情况下，所需的最少步数。 很显然直接暴力bfs模拟一遍最短路的情况就好了。

CODE

#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> #define fo(i,a,b) for (int i=a;i<=b;i++) #define N 105 using namespace std; const int Dire[8][2]{{2,1},{1,2},{2,-1},{-1,2},{1,-2},{-2,1},{-1,-2},{-2,-1}}; int f[N][N],g[N][N],a[N][N],d[N*N*N][2]; bool bz[N][N]; int n,m; int main() { freopen("lilypad.in","r",stdin); freopen("lilypad.out","w",stdout); scanf("%d%d",&n,&m); memset(f,127,sizeof(f)); int INF = f[1][1]; int edx,edy; fo(i,1,n) fo(j,1,m) { scanf("%d",&a[i][j]); if (a[i][j] == 3) d[1][0] = i,d[1][1] = j,bz[i][j] = true , f[i][j] = 0; else if (a[i][j] == 4) edx = i,edy = j; if (a[i][j] > 2) a[i][j] = 1; } int i = 0 ,j = 1,tmp = 0; while (i < j) { int x = d[++ i][0], y = d[i][1]; fo(k,0,7) { int xx = x + Dire[k][0], yy = y + Dire[k][1]; if (xx > 0 && xx <= n && yy > 0 && yy <= m && a[xx][yy] <= 1) { if (a[xx][yy] == 0) tmp = f[x][y] + 1; else tmp = f[x][y]; if (f[xx][yy] > tmp || (f[xx][yy] == tmp && g[x][y] + 1 < g[xx][yy])) { f[xx][yy] = tmp; g[xx][yy] = g[x][y] + 1; if (! bz[xx][yy]) bz[xx][yy] = true, d[++ j][0] = xx ,d[j][1] = yy; } } } bz[x][y] = false; } if (f[edx][edy] != INF) printf("%d %d\n",f[edx][edy],g[edx][edy]); else printf("-1 -1\n"); return 0; }