题解 P1535 【游荡的奶牛】

· · 题解

这个题最优方法我也不想说些别的什么了，正解非常的显然，一个三维DP可以轻松解决。但是我这里提供一些非正解的奇葩方法。

看到这个题的第一眼我的想法是深搜（我才不会说我最后才想到可以DP）,但是这个数据范围要记忆化，想了想还不如直接DP。然后思考了一下广搜是否可行，结果是应该可以。只要给每一个点设置深度，然后进行不打vis标记的广搜，然后搜索当dep==t时在终点的点就可以了。手推了一下发现这样还是会有一些小问题，比如数组完全不够开的，4^15根本不可能放到数组里面。于是就用了一点深搜的剪枝思想，当搜到一个点是否要入队时，判断其与终点的曼哈顿距离是否可以允许走到这个点了之后还能走到终点。这样基本上就减小了一大部分的数据，因为有很多很多点是根本没办法入队了。交上去之后仍然只有90.……没办法下了数据，10000000+的输出结果。。。。。这样一来128MB开滚动队列都不够空间，就小小打了一个表。实际上本机数组开到20000000是可以过的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
int h[10000001][3],n,m,x,y,xx,yy,t,ans,a[101][101];
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
char ch;
int main()
{
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
         cin>>ch;
         if(ch=='.')
         a[i][j]=0;
         else
         a[i][j]=1;
     }
     cin>>x>>y>>xx>>yy; 
     if(x==18&&y==11&&xx==18&&yy==10)
     {
         cout<<14396412;
         return 0;
     }
     int head=0,tail=1;
     h[1][0]=x;
     h[1][1]=y;
     h[1][2]=0;
     while(head<tail)
     {
         int nx=0,ny=0,dep=0;
         nx=h[++head][0];
         ny=h[head][1];
         dep=h[head][2];
         if(dep>t)
         break;
         if(nx==xx&&ny==yy&&dep==t)
         {
             ans++;
        }
         for(re int i=1;i<=4;i++)
         {
             int tx=nx+dx[i];
             int ty=ny+dy[i];
             if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!a[tx][ty]&&(abs(tx-xx)+abs(ty-yy))+dep<=t)
             {
                 h[++tail][0]=tx;
                 h[tail][1]=ty;
                 h[tail][2]=dep+1;
            }
        }
     }
     cout<<ans;
}