算法分析与设计PPT04-动态规划 - 12 FatMouse and Cheese.ppt

1、FatMouse在城市里储藏了一些奶酪在城市里储藏了一些奶酪。城城市是一个边长为市是一个边长为n的正方形网格：每个格子的位置标号是（的正方形网格：每个格子的位置标号是（p，q），），0pn，0qn。在每个格子有一个洞，。在每个格子有一个洞，FatMouse储藏着储藏着0100块块奶酪。现在它要享受美餐了。奶酪。现在它要享受美餐了。FatMouse从位置（从位置（0，0）开始吃。吃完所到之处的奶酪之后，它将沿）开始吃。吃完所到之处的奶酪之后，它将沿水平或垂直水平或垂直方向继续前进方向继续前进。有。有只叫做只叫做Top Killer的猫守的猫守在洞在洞穴附近。为穴附近。为了避免被了避免被Top K

2、iller抓到，每次它最多只能跑抓到，每次它最多只能跑k个网格。更糟糕的是：个网格。更糟糕的是：每吃完一处奶酪之后，每吃完一处奶酪之后，FatMouse就变得胖一些。为了得到充足的能量就变得胖一些。为了得到充足的能量到达下一站，他必须去一个比现在洞穴中奶酪到达下一站，他必须去一个比现在洞穴中奶酪更多的更多的位置。位置。给出给出n，k，及每个网格中奶酪的块数。计算，及每个网格中奶酪的块数。计算FatMouse在变肥得不能动在变肥得不能动之前，它最多能吃多少块奶酪之前，它最多能吃多少块奶酪。1FatMouse从位置（从位置（0，0）开始吃。吃完所到之处的奶酪之后，它）开始吃。吃完所到之处的奶酪之后

3、，它将沿将沿水平或垂直水平或垂直方向继续前进。每次它最多只能跑方向继续前进。每次它最多只能跑k个网格个网格，他必他必须去一个比现在洞穴中奶酪须去一个比现在洞穴中奶酪更多的更多的位置。位置。给出给出n，k，及每个网格中奶酪的块数。计算，及每个网格中奶酪的块数。计算FatMouse最多能吃多最多能吃多少块奶酪。少块奶酪。输入样例输入样例3 11 2 510 11 612 12 7-1-1输出样例输出样例372012012511011621212701201251101162121273437为了说明方便，将题目从（为了说明方便，将题目从（0，0）开始的坐标改成从）开始的坐标改成从（1，1）开始的坐

4、开始的坐标。题目中给出一个标。题目中给出一个 的网格，的网格，FatMouse在网格在网格（1，1）。）。它它每次在同一个方向上最多可以移动每次在同一个方向上最多可以移动k步，而且每次所到网格上的数字步，而且每次所到网格上的数字都要比上一次网格上的数字大。累计都要比上一次网格上的数字大。累计FatMouse所经过的网格上的数字所经过的网格上的数字输出即可。输出即可。（1）数据结构数据结构网格的大小和每次最多移动的步数：网格的大小和每次最多移动的步数：int n,k;网格矩阵，其值是该位置保存的奶酪数量：网格矩阵，其值是该位置保存的奶酪数量：int grid105105;301201251101

5、16212127（2）记忆式搜索）记忆式搜索记忆式搜索算法也称为备忘录记忆式搜索算法也称为备忘录方法。方法。使用数组使用数组mem保存已保存已经计算的结果：经计算的结果：int mem105105;实现记忆式搜索的函数是：实现记忆式搜索的函数是：int memSearch(int r,int c)其中形参其中形参(int r，int c)是当前的搜索位置。是当前的搜索位置。l 从从FatMouse当前的位置开始，每次向四周移动一步，直到移动当前的位置开始，每次向四周移动一步，直到移动k步为步为止止。l 在在每次移动时，判断下一步是不是在网格内，下一个位置奶酪的数每次移动时，判断下一步是不是在网格内，下一个位置奶酪的数量是不是比当前多，并且到下一个位置所获得的奶酪总数是不是比量是不是比当前多，并且到下一个位置所获得的奶酪总数是不是比当前位置多当前位置多。45