棋盘解题报告.doc

上次写了Linu_用vim进行C+编程的配置和操作入门后，今天再给棋盘写个解题报告试试。题目描述有一个m_m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费个金币。另外，你可以花费2个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用，而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？输入输出格式输入格式:数据的第一行包含两个正整数m，n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。其中c=代表黄色，c=0代表红色。相邻两个数之间用一个空格隔开盘左上角的坐标为（,），右下角的坐标为（m,m）。棋盘上其余的格子都是无色。保证棋盘的左上角，也就是（，）一颜色的。输出格式：输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出输入输出样例输入样例：570XXXX334044550输出样例：8y）的定是有。输入样例2：020XXXX3550输出样例2:-说明输入输出样例说明从（,）开始，走到（,2）不花费金币从（,2）向下走到（2,2）花费枚金币2枚金币从（2，2）施展魔法，将（2，3）变为黄色，花费从（2，2）走到（2，3）不花费金币从（2，3）走到（3，3）不花费金币从（3，3）走到（3，4）花费枚金币从（3,4）走到（4,4）花费枚金币从（4,4）施展魔法，将（4,5）变为黄色，花费2枚金币,从（4,4）走到（4,5）不花费金币从（4,5）走到（5,5）花费枚金币共花费8枚金币输入输出样例2说明从（,）走到（,2），不花费金币从（,2）走到（2,2），花费金币施展魔法将（2,3）变为黄色，并从（2,2）走到（2,3）花费2金币从（2,3）走到（3,3）不花费金币从（3,3）只能施展魔法到达（3,2）,（2,3）,（3,4）,（4,而从以上四点均无法到达（5,5），故无法到达终点，输出一数据规模与约定对于30%的数据，m5,nW0。对于60%的数据，m20,nW200。对于00%的数据，m00,nW,000。解题报告这道题目是20__年普及组第三题，实质上是求矩阵中一个点到另一个点的最短路径，对于这类型的题目，通常可以用搜索的方法来完成，深度优先和广度优先都行，广度优先需要使用队列，稍微复杂一点，我这里就用深搜来完成。

1、输入数据，构造棋盘，总共三种颜色，0表示红色，表示黄色，-表示无色；

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

3、对于魔法问题，我们采用一点贪心策略，碰到一个无色格子，就让他变得和当前格子颜色一样，再到深搜递归函数里面加上一个参数，来表示魔法状态，如果上次已经使用了魔法，而当前格子是无色，也需要使用魔法，因为不能两次使用魔法，就直接返回。

4、当走到了右下角（m,m）点，说明已经找到了一条路径，把花费最小那条路径记录下来就0K了。这道题目还是比较简单的，具体看代码：includeiostreamincludecstdioincludevcstringusingnamespacestd;inta0202,v0202,n,m,ans=999999;intd_=0,,0,-,dy=,0,-,0;按右下左上搜索单元格（_,y），从（,）到上一单元已花费va个单元颜色为c,上单元是否使用魔法movoiddfs(int_,inty,intval,intc,boolmo)if(a_y=-mo)不能两次魔法return;if(_=my二二m)inttemp=val;if(amm!=c)temp+;if(amm=-魔法，在原来基础上再加temp+;if(tempans)ans=temp;return;if(a_y=-)val+=2;mo=;elsemo=0;if(a_y!=c)val+=;c=a_y;if(val=v_yval=ans)return;elsev_y=val;int__,yy;for(inti=0;i4;i+)__=_+d_i;yy=y+dyi;if(__=__=myy=yy=m)dfs(__,yy,val,c,mo);intmaininti,_,y,k;cinmn;memset(a,-,sizeof(a)a数组全部设为-表示没有颜色memset(v,27,sizeof(v)v数组设为一个巨大的数字for(i=0;in;i+)scanf(%d%d%d,_,y,k);a_y=k;dfs(,,0,a,0);if(ans=999999)cout-;elsecoutans;