题目
为了让奶牛们娱乐和锻炼，约翰建造了一个美丽的池塘。这个池塘是矩形的，可以分成M×N个方格。一些格子是坚固得令人惊讶的莲花，还有一些是岩石，其余的只是美丽，纯净，湛蓝的水。
贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。
贝西的舞步很像象棋中的马步：每次跳跃可以横移2格，纵移1格，或纵移1格，横移2格，最多有八个方向可供移动选择。
约翰一直在观察贝西的芭蕾练习，发现她有时不能跳到终点，因为中间缺了一些必要的莲花。约翰可以多种一些莲花来帮助贝西到达终点。不过要。注意有石头的格子是不能种莲花的
请帮助约翰求出至少要添加几朵莲花才能让贝西跳到终点，记这个数字为L，再求出添加大号朵莲花后贝西跳到终点的最少步 ，记这个数字为J.最后求出添加大号朵莲花后跳到终点的步数为Ĵ的路线有多少条，记这个数字为W.
- 输入格式
第一行：两个用空格分开的整数：M和N，1≤M，N≤30
第二行到M + 1行：第i +1行有N个用空格分开的整数，描述了池塘第i行的状态：0为水，1为莲花，2为岩石，3为起点，4为终点。
- 输出格式
第一行：一个整数：L，即需要添加的最少莲花数目，如果无解输出-1
第二行：一个整数：J-，如果第一行是-1，输出不需要行这
第三行：一个整数：W，如果第一行是-1，不需要输出这行
- 示例输入
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
- 示例输出
2
6
2
分析：一开始很容易想到使用深收，但是超时了，不过还是提供下代码；然后我们可以想到用广搜来解决问题。
用f[ i ][ j ]记录走到 i , j 的状态怎么样；
用结构体保存当前到(x,y)的最小增加的荷花的数量、最小步数、在当前荷花数、步数的条件下的方案数（用long long）
那么每次广搜的时候更新只考虑三种情况：
1、当前点的荷花数比目标荷花数更优，那么直接照搬过来
2、当前点的荷花数和目标一样优，这样又要分三小点：
①当前点的步数比目标优，那么只要更新步数和方案数就好了
②当前点的步数和目标一样优，那么方案数加上去，其他原封不动
③当前点的步数不如目标优，那么直接不管它就好了
3、当前点的荷花数不如目标荷花数优，不管它
AC代码：
#include<stdio.h>
#include<queue>
#include<string.h>
#define INF 0x3f3f3f3f
using namespace std;
struct nod
{
int add;///增加的荷花数
int step;///步数
long long num;///多少的次数
}f[][];
struct noo
{
int x;
int y;
}q[];
bool book[][];///标记
int e[][];///建图
///方向数组 int ex,sx,ey,sy,n,m;
void DFS()///实际上是DFS+SPFA；
{
int net[][]={{-,},{-,},{,},{,},{,-},{,-},{-,-},{-,-}};
int head,tail,tx,ty,t;
head=tail=;
q[tail].x=sx;q[tail].y=sy;///起点进队列
tail++;
book[sx][sy]=;///标记
while(head<tail)///当队列不为空
{
int nx=q[head].x,ny=q[head].y;
head++;///出队
for(int k=;k<;k++)///枚举8个方向目标点
{
tx=net[k][]+nx;
ty=net[k][]+ny;
if(tx<||ty<||tx>n||ty>m||e[tx][ty]==)
continue;///越界与是障碍
///判断目标点是否为0或1
if(e[tx][ty]==)
t=;
else
t=;
///iF当前点的加花情况比目标点的好
///目标点照搬当前点
if(f[tx][ty].add>f[nx][ny].add+t)
{
f[tx][ty].add=f[nx][ny].add+t; f[tx][ty].step=f[nx][ny].step+; f[tx][ty].num=f[nx][ny].num;
if(book[tx][ty]==)
{
book[tx][ty]=;
q[tail].x=tx;
q[tail].y=ty;
tail++;
} }
///if当前点的荷花与目标点的荷花数一样
else if(f[tx][ty].add==f[nx][ny].add+t)
{
///当前点的步数比目标点的更少
///只要更新步数和方案数就好了
if(f[tx][ty].step>f[nx][ny].step+)
{
f[tx][ty].step=f[nx][ny].step+;
f[tx][ty].num=f[nx][ny].num;
if(book[tx][ty]==)
{
book[tx][ty]=;
q[tail].x=tx;
q[tail].y=ty;
tail++;
}
} ///当前点的步数和目标一样优，那么方案数加上去，其他原封不动
else if(f[tx][ty].step==f[nx][ny].step+)
{
f[tx][ty].num+=f[nx][ny].num;
if(book[tx][ty]==)
{
book[tx][ty]=;
q[tail].x=tx;
q[tail].y=ty;
tail++;
}
} }
}
book[nx][ny]=;///取消标记，因为我还可以走重复的点啊
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(book,,sizeof(book));
memset(f,,sizeof(f));
memset(q,,sizeof(q));
///建图与初始化
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&e[i][j]);
f[i][j].add=INF;
f[i][j].step=INF;
if(e[i][j]==)
{
sx=i;
sy=j;
f[i][j].add=;
f[i][j].step=;
f[i][j].num=;
}
if(e[i][j]==)
{
ex=i;
ey=j;
}
}
DFS();
if(f[ex][ey].add!=INF)
printf("%d\n%d\n%lld\n",f[ex][ey].add,f[ex][ey].step,f[ex][ey].num);
else
printf("-1\n");
}
}
深收超时的代码，虽然超时不过值得学习；
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int movex[]={,,,,-,-,-,-},movey[]={-,,-,,-,,-,};
int L=<<,J=<<,W,n,m,sx,sy,ex,ey,A[][],P[][];
void Dfs(int x,int y,int cnt,int tmp){
if (cnt>L) return;
if (cnt==L && tmp>J) return;
if (x==ex && y==ey){
if (cnt==L){
if (tmp==J) W++;
else if (tmp<J) J=tmp,W=;
}
else if (cnt<L) L=cnt,J=tmp,W=;
return;
}
for (int i=;i<;i++){
int xx=x+movex[i],yy=y+movey[i];
if (xx>= && xx<=n && yy>= && yy<=m && A[xx][yy]!= && P[xx][yy]==){
if (A[xx][yy]==){
P[xx][yy]=;
Dfs(xx,yy,cnt,tmp+);
P[xx][yy]=;
}
if (A[xx][yy]==){
P[xx][yy]=;
Dfs(xx,yy,cnt+,tmp+);
P[xx][yy]=;
}
}
}
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
for (int j=;j<=m;j++){
scanf("%d",&A[i][j]);
if (A[i][j]==) sx=i,sy=j,A[i][j]=;
if (A[i][j]==) ex=i,ey=j,A[i][j]=;
}
}
P[sx][sy]=;
Dfs(sx,sy,,);
if (L==<<) printf("-1");
else printf("%d\n%d\n%d",L,J,W);
fclose(stdin); fclose(stdout);
return ;
}
题后感想：
打的时候有了灵感应该抓住往下想。某种意义上深收与广搜相同，可以用做深搜的思想来做出广搜