企业官网建设流程全解析

P1535 Cow Travelling S

网页链接

P1535 Cow Travelling S

题目描述

奶牛们在被划分成N NN行M MM列（2 ≤ N , M ≤ 100 2 \leq N,M \leq 1002≤N,M≤100）的草地上游走， 试图找到整块草地中最美味的牧草。

Farmer John 在某个时刻看见贝茜在位置( R 1 , C 1 ) (R_1, C_1)(R1​,C1​)，恰好T TT（0 < T ≤ 15 0 \lt T \leq 150<T≤15）秒后，FJ 又在位置( R 2 , C 2 ) (R_2, C_2)(R2​,C2​)与贝茜撞了正着。FJ 并不知道在这T TT秒内贝茜是否曾经到过( R 2 , C 2 ) (R_2, C_2)(R2​,C2​)，他能确定的只是，现在贝茜在那里。

设S SS为奶牛在T TT秒内从( R 1 , C 1 ) (R_1, C_1)(R1​,C1​)走到( R 2 , C 2 ) (R_2, C_2)(R2​,C2​)所能选择的路径总数，FJ 希望有一个程序来帮他计算这个值。每一秒内，奶牛会水平或垂直地移动1 11单位距离（奶牛总是在移动，不会在某秒内停在它上一秒所在的点）。草地上的某些地方有树，自然，奶牛不能走到树所在的位置，也不会走出草地。

现在你拿到了一张整块草地的地形图，其中.表示平坦的草地，*表示挡路的树。你的任务是计算出，一头在正好T TT秒从( R 1 , C 1 ) (R_1, C_1)(R1​,C1​)移动到( R 2 , C 2 ) (R_2, C_2)(R2​,C2​)的奶牛可能经过的路径有哪些。

输入格式

第一行包含3 33个用空格隔开的整数：N , M , T N,M,TN,M,T。

接下来N NN行：第i ii行为M MM个连续的字符，描述了草地第i ii行各点的情况，保证字符是.和*中的一个。

最后一行4 44个整数R 1 , C 1 , R 2 , C 2 R_1,C_1,R_2,C_2R1​,C1​,R2​,C2​。

输出格式

输出从( R 1 , C 1 ) (R_1, C_1)(R1​,C1​)移动到( R 2 , C 2 ) (R_2, C_2)(R2​,C2​)的方案数。

输入输出样例 #1

输入 #1

4 5 6 ...*. ...*. ..... ..... 1 3 1 5

输出 #1

1

说明/提示

奶牛在正好6 66秒从( 1 , 3 ) (1,3)(1,3)走到( 1 , 5 ) (1,5)(1,5)的方法只有一种，绕过她面前的树。

解题思路

本题是带限制步数的网格路径计数问题，要求在恰好T TT步内从起点走到终点，且不能经过障碍物。由于T ≤ 15 T \le 15T≤15极小，直接采用记忆化搜索（DFS + 剪枝）即可高效求解。

1. 问题等价转化

• 移动规则：每秒必须向上下左右四个方向之一移动1 11单位，不能停留，不能出界，不能进入树所在的格子。
• 目标：计算从( R 1 , C 1 ) (R_1, C_1)(R1​,C1​)出发，恰好经过T TT秒到达( R 2 , C 2 ) (R_2, C_2)(R2​,C2​)的所有不同路径数。
• 状态定义：定义dp[x][y][t]表示在时刻t tt位于格子( x , y ) (x, y)(x,y)时，从当前状态走到终点的合法路径数。显然初始调用为dfs(R1, C1, 0)。
• 边界条件：
  • 若t = T t = Tt=T：当( x , y ) = ( R 2 , C 2 ) (x, y) = (R_2, C_2)(x,y)=(R2​,C2​)时返回1 11，否则返回0 00。
  • 若当前剩余时间T − t T - tT−t小于曼哈顿距离∣ x − R 2 ∣ + ∣ y − C 2 ∣ |x - R_2| + |y - C_2|∣x−R2​∣+∣y−C2​∣，即使直线无阻碍也无法及时到达，可直接剪枝返回0 00。
  • 若当前状态已计算过（记忆化数组不为− 1 -1−1），直接返回。

2. 算法实现

1. 建图与标记：读入N , M , T N, M, TN,M,T，用bitset或布尔数组b[i][j]标记障碍物（树）。
2. 记忆化搜索dfs(x, y, tm)：
   • 若re[x][y][tm] != -1，直接返回。
   • 剪枝：若曼哈顿距离大于剩余步数，re[x][y][tm] = 0并返回。
   • 若tm == T：检查是否到达终点，返回1 11或0 00。
   • 若tm < T：向四个合法邻格递归，累加结果。
   • 将结果存入re[x][y][tm]并返回。
3. 输出：输出dfs(R1, C1, 0)。

3. 复杂度分析

• 状态数：最多N × M × T ≈ 100 × 100 × 15 = 1.5 × 10 5 N \times M \times T \approx 100 \times 100 \times 15 = 1.5 \times 10^5N×M×T≈100×100×15=1.5×105，每个状态最多扩展4 44次，总计算量极小。
• 剪枝效果：曼哈顿距离剪枝会大幅缩减实际搜索空间，使程序在极短时间内完成。
• 空间复杂度：O ( N × M × T ) O(N \times M \times T)O(N×M×T)用于记忆化存储，完全可行。

总结

利用T TT极小的特点，直接三维记忆化搜索路径数。曼哈顿距离剪枝能有效剔除不可能到达的状态，避免无效搜索。整体思路简单直接，完美匹配数据范围。

代码简要说明

1. 全局变量：
   • b[i][j]：记录障碍物位置。
   • re[x][y][tm]：记忆化数组，初始化为− 1 -1−1。
2. DFS 函数：
   • 若已有记录则直接返回。
   • 曼哈顿距离剪枝。
   • tm == T时返回终点判断结果。
   • 遍历四个方向，对可走的邻格递归累加路径数。
   • 存入记忆化数组并返回。
3. 主函数：
   • 读入地图并标记障碍物。
   • 调用dfs(R1, C1, 0)并输出结果。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll dx[4]={1,-1,0,0};constll dy[4]={0,0,1,-1};ll n,m,t,r1,c1,r2,c2;bitset<108>b[108];ll re[108][108][20];lldfs(ll x,ll y,ll tm){if(re[x][y][tm]!=-1)returnre[x][y][tm];if(abs(x-r2)+abs(y-c2)>t-tm)returnre[x][y][tm]=0;if(tm>t)returnre[x][y][tm]=0;if(tm==t){if(x==r2&&y==c2)returnre[x][y][tm]=1;elsereturnre[x][y][tm]=0;}ll ans=0;for(ll i=0;i<4;i++){if(b[x+dx[i]][y+dy[i]]||x+dx[i]<1||x+dx[i]>n||y+dy[i]<1||y+dy[i]>m)continue;ans+=dfs(x+dx[i],y+dy[i],tm+1);}returnre[x][y][tm]=ans;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m>>t;memset(re,-1,sizeof(re));for(ll i=1;i<=n;i++){string s;cin>>s;for(ll j=0;j<m;j++)if(s[j]=='*')b[i][j+1]=1;}cin>>r1>>c1>>r2>>c2;cout<<dfs(r1,c1,0)<<endl;return0;}