取方格数类题目

取方格数类题目

一、 题目原型 棋盘路径

有一个n*m的棋盘，左上角为（1,1），由下角为（n,m）。有一颗棋子，初始位置为（1,1），该棋子只能向右走或者向下走，问该棋子从（1,1）到（n,m）一共有几条路径？ （1,1） (n,m)

输入：两个整数n 和m 输出：一个数，路径总数

解题思路：

除左边界和上边界上的点的路径，为其上面点的路径同左边点路径之和。 （1,1） (i-1,j) (I,j-1) (I,j) (n,m)

递推公式为：f(I,j)=f(I-1,j)+f(I,j-1) 边界条件：f(1,1)=1

二、 算法拓展 见P1372 最小伤害

三、 增加决策多样性 见P1370 方格取数

四、 增加控制点 见P1127 马拦过河卒 最小花费

现在有一个n*m的矩形棋盘，每个格子上面都有一个非负整数，你拥有一枚棋子，在游戏开始的时候，你的棋子位于左上角的方格内，游戏的规则很简单：每一次，你可以将棋子向右或向下移动一格，当棋子到达右下角的方格时，游戏

结束。同时，你必须保证你的棋子通过的路径是花费最小的。一条路径的花费就是这条路径上所有格子上的数字的和。有一点需要说明的是，被标记为0的格子是不可以走到的。

五、增加线程

见P1373 二取方格数 P1115 三取方格数 P1177 传纸条

六、增加“数学佐料” 方格取数

现在有一个n*n的正方形棋盘，每个格子上面都有一个非负整数。你拥有一枚棋子，在游戏开始的时候，你的棋子位于左上角的方格内，游戏的规则很简单：每一次，你可以将棋子向右或向下移动一格，当棋子到达右下角的方格时，游戏结束。同时，你必须保证你的棋子通过的路径是花费最小的。一条路径的花费就是这条路径上所有格子上的数字的乘积最后的连续的0的个数。有一点需要说明的是，被标记为0的格子是不可以走到的。

输入：第一行为一个整数n (1<=n<=1000)，表示棋盘的大小。下面n 行每行有n 个整数，表示每个格子上的数字（均不超过1000000）。

输出：一个正整数，表示找到的最优路径的费用 样例输入： 4

1 3 0 0 0 8 2 25 6 5 0 3 0 15 7 4 样例输出 2

本文来源：https://www.bwwdw.com/article/1ljv.html