题目大意：

从一个点走到另一个点，必须要在限制时间内走完，并且不能撞到障碍物上，问有多少种方法。

此题有两种算法可以做，我将都为大家介绍。（其实两种思路都差不多，只是算法不同而已，一个是宽（广）搜，一个是动规）

第一种方法BFS：

递归每一个点，如果这个点还可以通往其他没有障碍物的话，就继续递归下去，否则返回。如果到达目的地就直接Return。

代码如下

#include <bits/stdc++.h>//万能头文件
using namespace std;//常规
int jsq,cnt,k;//定义变量
char e[255][255];//字符数组
int n,m,st1,st2,de1,de2;//起点与终点
int xx[5]={0,-1,0,1};
int yy[5]={-1,0,1,0};//打表
void zou(int x,int y,int z)//递归函数
{
    if(z==k)//如果体力已尽或已到达目的地就Return
    {
        if(x==de1&&y==de2)
        {
            jsq++; //但如果到达方法就+1
        }
        return ;//返回
    }
    for(int i=0;i<4;i++)//枚举
    {
        int dx=x+xx[i],dy=y+yy[i];
        if(dx>=1&&dy>=1&&dx<=n&&dy<=m&&e[dx][dy]=='.')//如果可以继续递归就继续下去，如果不能就枚举下一个点
        {
            zou(dx,dy,z+1);//继续下去
        }
    }
}
int main()//主函数
{
    cin>>n>>m>>k;//输入长宽以及体力
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>e[i][j];//输入是否可走
        }
    }
    cin>>st1>>st2>>de1>>de2;//输入起点终点
    zou(st1,st2,0);//递归
    cout<<jsq;//输出方法总数
    return 0;//结束
}

但是我们发现以上代码只能得40分，若开O2优化可得50分（阴招），怎么优化呢？

咱们做一个假设，如果体力值还剩五个单位，而路程还剩十五个单位，那么肯定走不了，所以我们只要加一个判断就可以了。

AC Code：

#include <bits/stdc++.h>//万能头文件
using namespace std;//常规
int jsq,cnt,k;//定义变量
char e[255][255];//字符数组
int n,m,st1,st2,de1,de2;//起点与终点
int xx[5]={0,-1,0,1};
int yy[5]={-1,0,1,0};//打表
void zou(int x,int y,int z)//递归函数
{
    if(z==k)//如果体力已尽或已到达目的地就Return
    {
        if(x==de1&&y==de2)
        {
            jsq++; //但如果到达方法就+1
        }
        return ;//返回
    }
    if(z+abs(x-de1)+abs(y-de2)>k)//如果路程比体力多，那么肯定不行，直接Return
    return ;
    for(int i=0;i<4;i++)//枚举
    {
        int dx=x+xx[i],dy=y+yy[i];
        if(dx>=1&&dy>=1&&dx<=n&&dy<=m&&e[dx][dy]=='.')//如果可以继续递归就继续下去，如果不能就枚举下一个点
        {
            zou(dx,dy,z+1);//继续下去
        }
    }
}
int main()//主函数
{
    cin>>n>>m>>k;//输入长宽以及体力
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>e[i][j];//输入是否可走
        }
    }
    cin>>st1>>st2>>de1>>de2;//输入起点终点
    zou(st1,st2,0);//递归
    cout<<jsq;//输出方法总数
    return 0;//结束
}

此题还有一种做法就是直接DP，思路和前面的BFS一样（如果这个点还可以通往其他没有障碍物的话就把值存储下来，并判断可否到达终点），只是这个是直接枚举，而上一个是递归，这样还可以节省时间（BFS花了833毫秒，而DP只用了32毫秒），并且也十分简单，用一个数组存储答案，一个数组进行判断，最后直接输出终点存储的值即可。

Another AC Code

#include <bits/stdc++.h>//万能头文件
using namespace std;//常规
int xx[5]={0,0,-1,0,1};
int yy[5]={0,-1,0,1,0};//照样打表
int main()
{
    int n,m,k;
    cin>>n>>m>>k;//输入长宽以及体力
    int a[n+5][m+5],b[n+5][m+5];//定义两个数组，以用来存储，一个用来判断
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));//清空两个数组
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;//可以节约空间
            if(c=='*')//转换一下
            b[i][j]=a[i][j]=-1;//输入并存储是否可走
        }
    }
    int st1,st2,de1,de2;
    cin>>st1>>st2>>de1>>de2;//输入起点以及终点
    b[st1][st2]=a[st1][st2]=1;//起点值为1
    for(int i=1;i<=k;i++)//枚举步数，如果步数没了就可以自动跳出
    {
        for(int j=1;j<=n;j++)
        {
            for(int p=1;p<=m;p++)//枚举每个点的横竖坐标
            {
                if(a[j][p]!=-1)//如果可以走就枚举那个点附近的点
                {
                    b[j][p]=0;//复制成零（方便计算）
                    for(int q=1;q<=4;q++)//枚举方向
                    {
                        int dx=j+xx[q],dy=p+yy[q];//把每个方向的坐标都算出来
                        if(a[dx][dy]!=-1)//如果可以就存储答案
                        b[j][p]+=a[dx][dy];//存储答案
                    }
                }
            }
        }
        for(int s=1;s<=n;s++)
        {
            for(int t=1;t<=m;t++)
            {
                a[s][t]=b[s][t];//把B的值赋值给A，并继续计算
            }
        }
    }
    cout<<a[de1][de2];//直接输出终点的方案数（重点所存储的值
    return 0;//结束
 }

ps：写了一个晚上，求过。。。

珍惜账号，远离抄袭！