题解 P1535 【游荡的奶牛】

这题虽然简单,但是题解有点少,我来一个递推;

这道题就是一个简单的宽搜;

但是实现的方式不再用队列而已;

不然会很难操作;

所以就变成了递推;

我们令f[i][j][k]代表在(i,j)这个点用k步到达的方式;

这样我想到一道过河卒的题;

那道题也是一个递推;

不过那道题是二维,没有步数限制;

即当前点可以由上下左右四个点中合法的点经过一步走过来;

所以我们可以直接暴力递推就好了;

先判断合不合法;

合法就加过来,否则就换下一个点继续判断;

最后输出目标点目标步数的方式就好了;

至于搜索,我没有写,我觉得那样子不是很有趣;

#include<iostream>
#include<cstdio>
#include<algorithm>
#define II int
#define C char
#define R register
#define I 105
using namespace std;

II f[I][I][20];
II bx[4]={1,-1,0,0};
II by[4]={0,0,1,-1};

C map[I][I];

II n,m,t,sx,sy,tx,ty;

int main()
{
//    freopen("1.in","r",stdin);

    scanf("%d%d%d",&n,&m,&t);
    for(R II i=1;i<=n;i++)
    {
        for(R II j=1;j<=m;j++)
        {
            cin>>map[i][j];
        }
    } 
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

    f[sx][sy][0]=1;
    for(R II i=1;i<=t;i++)
    {
        for(R II j=1;j<=n;j++)
        {
            for(R II k=1;k<=m;k++)
            {
                if(map[j][k]!='*') for(R II l=0;l<=3;l++)
                {
                    R II x=j+bx[l];
                    R II y=k+by[l];
                    if(x&&y&&x<=n&&y<=m&&map[x][y]!='*') {
                        // 合法,加步数; 
                        f[j][k][i]+=f[x][y][i-1];
                    }
                }
            }
        }
    }

    printf("%d\n",f[tx][ty][t]);
    exit(0);
}

发表于 2017-09-21 10:25:57 in 题解