他只是说
>奶牛总是在移动，不会在某秒内停在它上一秒所在的点
您的算法把他走回头路的情况排除掉了，但是这种情况是可以的。
正解的话使用这种朴素搜索貌似有点麻烦。
by Maxmilite @ 2021-03-14 15:43:35
这里我在您的代码上搞了一个类似于启发式搜索的东西。
判断当前位置距离目标位置的曼哈顿距离和剩余时间的关系。
不是正解，只有开 $O2$ 才勉强能过。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N= 200;
char mp[N][N];
int vis[N][N];
int d[][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,t,sx,sy,ex,ey,cnt;
inline int Abs(int x)
{
if (x < 0)
return -x;
else
return x;
}
inline int dis(int x, int y)
{
return Abs(x - ex) + Abs(y - ey);
}
void dfs(int x,int y,int len)
{
if(len>t) return ;
if(x==ex&&y==ey&&len==t)
{
cnt++;
return ;
}
if (dis(x, y) + len > t)
return;
for(int i=0;i<4;i++)
{
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m /*&&!vis[dx][dy]*/ && mp[dx][dy] == '.')
{
// vis[dx][dy]=1;
dfs(dx,dy,len+1);
// vis[dx][dy]=0;
}
}
}
int main()
{
cin>>n>>m>>t;
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
cin>>sx>>sy>>ex>>ey;
dfs(sx,sy,0);
printf("%d\n",cnt);
return 0;
}
```
by Maxmilite @ 2021-03-14 15:47:30
[不开O2 T飞](https://www.luogu.com.cn/record/47851227)
[开O2](https://www.luogu.com.cn/record/47851275)
by Maxmilite @ 2021-03-14 15:48:14
@[h1910819075](/user/286752)
by Maxmilite @ 2021-03-14 15:48:21
@[Maxmilite](/user/274993) 好的，谢谢，我看看
by h1910819075 @ 2021-03-14 15:50:20
这是写了一点简单卡常的代码
不开 $O2$ 勉强过线
```cpp
#include <bits/stdc++.h>
using namespace std;
#define regint register int
char mp[105][105];
int d[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m, t, sx, sy, ex, ey, cnt;
inline int Abs(int x)
{
return x < 0 ? -x : x;
}
inline int dis(int x, int y)
{
return Abs(x - ex) + Abs(y - ey);
}
void dfs(int x, int y, int len)
{
if (dis(x, y) + len > t)
return;
if (x == ex && y == ey && len == t)
{
++cnt;
return;
}
for (regint i(0); i < 4; ++i)
{
int dx = x + d[i][0];
int dy = y + d[i][1];
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && mp[dx][dy] == '.')
dfs(dx, dy, len + 1);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> t;
for (regint i(1); i <= n; ++i)
cin >> mp[i] + 1;
cin >> sx >> sy >> ex >> ey;
dfs(sx, sy, 0);
cout << cnt << endl;
return 0;
}
```
[记录详情](https://www.luogu.com.cn/record/47852280)
by Maxmilite @ 2021-03-14 15:56:44
@[Maxmilite](/user/274993) 我知道了，谢谢你，这个题目实际上是要求在T秒时，能到达终点的路线有多少条，而我的程序排除了可以回到之前路线的方案，这题的数据范围有点小，如果再大一点的话，照我这样的代码是过不了，但是啊，我就想是不是可以开一个三维数组，像DP一样，在K秒里到达(x,y)的方案数又多少，一直递推到终点，况且这个数据范围才是100，可以开三维的数组，对吧？
by h1910819075 @ 2021-03-14 17:07:04
@[h1910819075](/user/286752)
应该是可以的
用 $f[i][j][k]$ 表示在第 $k$ 秒的时候走到 $(i, j)$ 的情况数，存在方程 $f[i][j][k] = f[i + (-1, 1)][j + (-1, 1)][k - 1]$
然后最后输出 $f[ex][ey][t]$ 就可以了
by Maxmilite @ 2021-03-14 17:11:55
@[Maxmilite](/user/274993) 这个方程应该不太对，因为不能保证f[i+(−1,1)][j+(−1,1)]这个位置有没有树，但是这个方程有点是那个意思，我理解了
by h1910819075 @ 2021-03-14 17:31:18
怎么会这样呢？不行，超时了一个点（[点这里](https://www.luogu.com.cn/record/47861341)）
```
#include<bits/stdc++.h>
using namespace std;
const int N=100+10;
int dp[N][N][20];
int d[][2]={{1,0},{-1,0},{0,1},{0,-1}};
char mp[N][N];
int n,m,t,sx,sy,ex,ey;
struct node{
int x,y;
int k;
node(int a,int b,int c)
{
x=a,y=b,k=c;
}
};
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
queue<node> q;
q.push(node(sx,sy,0));
dp[sx][sy][0]=1;
while(!q.empty())
{
node now=q.front();
q.pop();
if(now.x==ex&&now.y==ey&&now.k==t)
{
printf("%d",dp[now.x][now.y][now.k]);
return 0;
}
for(int i=0;i<4;i++)
{
int dx=now.x+d[i][0];
int dy=now.y+d[i][1];
int dt=now.k+1;
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&mp[dx][dy]!='*')
{
if(dp[dx][dy][dt])
{
dp[dx][dy][dt]+=dp[now.x][now.y][now.k];
}
else
{
dp[dx][dy][dt]=dp[now.x][now.y][now.k];
q.push(node(dx,dy,dt));
}
}
}
}
}
by h1910819075 @ 2021-03-14 17:33:25