棋盘解题报告noip普及组第三题.doc
9页
棋盘解题报告（noip2017普及组第三题）上次写了 Linux用vim进行C++编程的配置和操作入门后，今天再给棋盘写个 解题报告试试题目描述有一个m x m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的你现在要从棋盘的最左上角走到棋盘的最右下角任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、下、左、右四个方向前进当你从一个格子走向另一个格子时，如果两个 格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1个金币另外，你可以花费2个金币施展魔法让下一个无色格子暂时变为你指定的颜色 但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你 使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只 有当你离开这个位置，走到一个本来就有颜色的格子上的时候， 你才能继续使用 这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个 格子恢复为无色现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？输入输出格式输入格式:数据的第一行包含两个正整数 m ， n ，以一个空格分开， 分别代表棋盘的大小， 棋盘上有颜色的格子的数量。
接下来的 n 行，每行三个正整数 x， y， c， 分别表示坐标为（ x， 格子有颜色 c其中 c=1 代表黄色， c=0 代表红色 相邻两个数之间用一个空格隔开 盘左上角的坐标为（ 1, 1 ），右下角的坐标为（ m, m ）棋盘上其余的格子都是无色保证棋盘的左上角，也就是（ 1 ， 1） 一颜色的输出格式：输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出输入输出样例输入样例 #1 ：5 71 1 01 2 02 2 13 3 13 4 04 4 15 5 0输出样例 #1 ：8y）的定是有1输入样例 #2 ：1 1 01 2 02 2 13 3 15 5 0输出样例#2 :-1说明输入输出样例1说明从（1, 1）开始，走到（1 , 2）不花费金币从（1, 2）向下走到（2, 2）花费1枚金币2枚金币从（2， 2）施展魔法，将（2， 3）变为黄色，花费从（2， 2）走到（2， 3）不花费金币从（2， 3）走到（3， 3）不花费金币从（3， 3）走到（3， 4）花费1枚金币从（3, 4）走到（4, 4）花费1枚金币从（4, 4）施展魔法，将（4, 5）变为黄色，花费2枚金币,从（4, 4）走到（4, 5）不花费金币从（4, 5）走到（5, 5）花费1枚金币共花费8枚金币输入输出样例2说明从（1, 1 ）走到（1 , 2），不花费金币从（1, 2）走到（2, 2），花费1金币施展魔法将（2, 3）变为黄色，并从（2 , 2）走到（2, 3）花费2金币从（2, 3）走到（3, 3）不花费金币从（3 , 3）只能施展魔法到达（3 , 2）, （ 2 , 3） , （ 3 , 4） , （ 4 ,而从以上四点均无法到达（5, 5），故无法到达终点，输出一1数据规模与约定对于 30% 的数据，1 < m < 5, 1 < nW 10。
对于 60% 的数据，1 < m < 20, 1 < n W 200对于 100% 的数据，1 < m < 100 , 1 < nW 1,000解题报告这道题目是2017年普及组第三题，实质上是求矩阵中一个点到另一个点的最短 路径，对于这类型的题目，通常可以用搜索的方法来完成，深度优先和广度优先 都行，广度优先需要使用队列，稍微复杂一点，我这里就用深搜来完成1、 输入数据，构造棋盘，总共三种颜色，0表示红色，1表示黄色，-1表示无色；2、 从（1,1 ）点开始，往上下左右四个方向去搜索，这里和普通的只能往右和左搜索的题目有点不同，在普通的搜索里面，到达了一个点就设一个标志变量， 然 后下次就不再搜索这个节点，但是这里不能这么简单的处理，因为每个节点可以 往上下左右四个方向搜索，如果不设标志则会形成死循环，出不来，设个标志则 有可能从不同的路径走到这个点的花费可能不相同， 第一次的花费不一定是最低 的那么我们就把进到这个节点的花费记录下来， 下次进入这个节点时候，比较一下花费，如果相同或者大于上次花费，就不用搜索这个节点，否则就继续搜索 他，我们把这种方法叫做记忆化搜索3、对于魔法问题，我们采用一点贪心策略，碰到一个无色格子，就让他变得和当前格子颜色一样，再到深搜递归函数里面加上一个参数， 来表示魔法状态，如 果上次已经使用了魔法，而当前格子是无色，也需要使用魔法，因为不能两次使 用魔法，就直接返回。
4、当走到了右下角（m,m ）点，说明已经找到了一条路径，把花费最小那条路 径记录下来就0K 了这道题目还是比较简单的，具体看代码：#in clude
