棋盘解题报告(noip2017普及组第三题)

1、棋盘解题报告（noip2017普及组第三题）上次写了 Linux用vim进行C+编程的配置和操作入门后，今天再给棋盘写个 解题报告试试。题目描述有一个m x m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个 格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1个金币。另外，你可以花费2个金币施展魔法让下一个无色格子暂时变为你指定的颜色。 但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就

2、是说，如果你 使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只 有当你离开这个位置，走到一个本来就有颜色的格子上的时候， 你才能继续使用 这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个 格子恢复为无色。现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？输入输出格式输入格式:数据的第一行包含两个正整数 m ， n ，以一个空格分开， 分别代表棋盘的大小， 棋盘上有颜色的格子的数量。接下来的 n 行，每行三个正整数 x， y， c， 分别表示坐标为（ x， 格子有颜色 c。其中 c=1 代表黄色， c=0 代表红色。 相邻两个数之

3、间用一个空格隔开 盘左上角的坐标为（ 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）施展魔法，

4、将（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

5、） , （ 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 ）点

6、开始，往上下左右四个方向去搜索，这里和普通的只能往右和左搜索的题目有点不同，在普通的搜索里面，到达了一个点就设一个标志变量， 然 后下次就不再搜索这个节点，但是这里不能这么简单的处理，因为每个节点可以 往上下左右四个方向搜索，如果不设标志则会形成死循环，出不来，设个标志则 有可能从不同的路径走到这个点的花费可能不相同， 第一次的花费不一定是最低 的。那么我们就把进到这个节点的花费记录下来，下次进入这个节点时候，比较一下花费，如果相同或者大于上次花费，就不用搜索这个节点，否则就继续搜索 他，我们把这种方法叫做记忆化搜索3、对于魔法问题，我们采用一点贪心策略，碰到一个无色格子，就让他变得和当前格子

7、颜色一样，再到深搜递归函数里面加上一个参数， 来表示魔法状态，如 果上次已经使用了魔法，而当前格子是无色，也需要使用魔法，因为不能两次使 用魔法，就直接返回。4、当走到了右下角（m,m ）点，说明已经找到了一条路径，把花费最小那条路 径记录下来就0K 了。这道题目还是比较简单的，具体看代码：#in clude#in clude#in cludevcstri ngusing n amespace std;int a102102,v102102, n,m,a ns=999999;int dx=0,1,0,-1,dy=1,0,-1,0;按右下左上搜索/搜索单元格（x,y），从（1,1）到上一单元已花

8、费val/上个单元颜色为c,上单元是否使用魔法mo void dfs(i nt x, int y, int val, i nt c, bool mo)if(axy = -1 & mo)不能两次魔法return;if(x=m&y二二m)int temp=val;if(amm != c)temp+;if(amm=-1)/ 变魔法，在原来基础上再加 1temp+;if(temp=vxy | val=ans)return;elsevxy = val;int xx,yy;for(int i=0; i=1&xx=1&yymn;memset(a, -1, sizeof(a);/ 把 a 数组全部设为 -1 表示没有颜色 memset(v, 127,