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 TT0 T ≤ 15 0 \lt T \leq 150T≤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输入 #14 5 6 ...*. ...*. ..... ..... 1 3 1 5输出 #11说明/提示奶牛在正好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 TtT当( 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. 算法实现建图与标记读入N , M , T N, M, TN,M,T用bitset或布尔数组b[i][j]标记障碍物树。记忆化搜索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]并返回。输出输出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×151.5×105每个状态最多扩展4 44次总计算量极小。剪枝效果曼哈顿距离剪枝会大幅缩减实际搜索空间使程序在极短时间内完成。空间复杂度O ( N × M × T ) O(N \times M \times T)O(N×M×T)用于记忆化存储完全可行。总结利用T TT极小的特点直接三维记忆化搜索路径数。曼哈顿距离剪枝能有效剔除不可能到达的状态避免无效搜索。整体思路简单直接完美匹配数据范围。代码简要说明全局变量b[i][j]记录障碍物位置。re[x][y][tm]记忆化数组初始化为− 1 -1−1。DFS 函数若已有记录则直接返回。曼哈顿距离剪枝。tm T时返回终点判断结果。遍历四个方向对可走的邻格递归累加路径数。存入记忆化数组并返回。主函数读入地图并标记障碍物。调用dfs(R1, C1, 0)并输出结果。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll dx[4]{1,-1,0,0};constll dy[4]{0,0,1,-1};ll n,m,t,r1,c1,r2,c2;bitset108b[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(tmt)returnre[x][y][tm]0;if(tmt){if(xr2yc2)returnre[x][y][tm]1;elsereturnre[x][y][tm]0;}ll ans0;for(ll i0;i4;i){if(b[xdx[i]][ydy[i]]||xdx[i]1||xdx[i]n||ydy[i]1||ydy[i]m)continue;ansdfs(xdx[i],ydy[i],tm1);}returnre[x][y][tm]ans;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnmt;memset(re,-1,sizeof(re));for(ll i1;in;i){string s;cins;for(ll j0;jm;j)if(s[j]*)b[i][j1]1;}cinr1c1r2c2;coutdfs(r1,c1,0)endl;return0;}
P1535 Cow Travelling S【洛谷算法习题】
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 TT0 T ≤ 15 0 \lt T \leq 150T≤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输入 #14 5 6 ...*. ...*. ..... ..... 1 3 1 5输出 #11说明/提示奶牛在正好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 TtT当( 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. 算法实现建图与标记读入N , M , T N, M, TN,M,T用bitset或布尔数组b[i][j]标记障碍物树。记忆化搜索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]并返回。输出输出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×151.5×105每个状态最多扩展4 44次总计算量极小。剪枝效果曼哈顿距离剪枝会大幅缩减实际搜索空间使程序在极短时间内完成。空间复杂度O ( N × M × T ) O(N \times M \times T)O(N×M×T)用于记忆化存储完全可行。总结利用T TT极小的特点直接三维记忆化搜索路径数。曼哈顿距离剪枝能有效剔除不可能到达的状态避免无效搜索。整体思路简单直接完美匹配数据范围。代码简要说明全局变量b[i][j]记录障碍物位置。re[x][y][tm]记忆化数组初始化为− 1 -1−1。DFS 函数若已有记录则直接返回。曼哈顿距离剪枝。tm T时返回终点判断结果。遍历四个方向对可走的邻格递归累加路径数。存入记忆化数组并返回。主函数读入地图并标记障碍物。调用dfs(R1, C1, 0)并输出结果。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll dx[4]{1,-1,0,0};constll dy[4]{0,0,1,-1};ll n,m,t,r1,c1,r2,c2;bitset108b[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(tmt)returnre[x][y][tm]0;if(tmt){if(xr2yc2)returnre[x][y][tm]1;elsereturnre[x][y][tm]0;}ll ans0;for(ll i0;i4;i){if(b[xdx[i]][ydy[i]]||xdx[i]1||xdx[i]n||ydy[i]1||ydy[i]m)continue;ansdfs(xdx[i],ydy[i],tm1);}returnre[x][y][tm]ans;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnmt;memset(re,-1,sizeof(re));for(ll i1;in;i){string s;cins;for(ll j0;jm;j)if(s[j]*)b[i][j1]1;}cinr1c1r2c2;coutdfs(r1,c1,0)endl;return0;}
