棋盘解题报告(noip2017普及组第三题)
剑侠情缘3生活技能-很傻
棋盘解题报告（noip2017普及组第三题）
上次写了Linux用vim进行C
++编程的配置和操作入门后，今天再给棋盘写个
解题报告试试。
题目描述
有一个m × m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色
的。你现在要从
棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向
上、 下、左、
右四个方向前进。当你从一个格子走向另一个格子时，如果两个
格子的颜色相同，那你不需要花费金币；
如果不同，则你需要花费 1 个金币。
另外， 你可以花费 2
个金币施展魔法让下一个无色格子暂时变为你指定的颜色。
但这个魔法不能连续使用， 而且这个魔法的
持续时间很短，也就是说，如果你
使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用
魔法； 只
有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用
这个
魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个
格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？
输入输出格式
输入格式：
数据的第一行包含两个正整数 m，
n，以一个空格分开，分别代表棋盘的大小，
棋盘上有颜色的格子的数量。
接下来的 n
行，每行三个正整数 x， y， c， 分别表示坐标为（ x， y）的
格子有颜色 c。
其中 c=1 代表黄色， c=0 代表红色。 相邻两个数之间用一个空格隔开。
棋
盘左上角的坐标为（ 1, 1），右下角的坐标为（ m, m）。
棋盘上其余的格子都是无色。保证棋盘的左上角，也就是（ 1， 1） 一定是有
颜色的。
输出格式：
输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出-1。
输入输出样例
输入样例#1：
5 7
1 1 0
1 2
0
2 2 1
3 3 1
3 4 0
4 4 1
5 5
0
输出样例#1：
8
输入样例#2：
5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0
输出样例#2：
-1
说明
输入输出样例 1
说明
从（ 1， 1）开始，走到（ 1， 2）不花费金币
从（ 1，
2）向下走到（ 2， 2）花费 1 枚金币
从（ 2， 2）施展魔法，将（ 2，
3）变为黄色，花费 2 枚金币
从（ 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，
3）
而从以上四点均无法到达（ 5，
5），故无法到达终点，输出－1
数据规模与约定
对于 30%的数据， 1 ≤ m ≤
5， 1 ≤ n ≤ 10。
对于 60%的数据， 1 ≤ m ≤ 20， 1 ≤ n ≤
200。
对于 100%的数据， 1 ≤ m ≤ 100， 1 ≤ n ≤ 1,000。
解题报告
这道题目是2017年普及组第三题，实质上是求矩阵中一个点到另一个点
的最短
路径，对于这类型的题目，通常可以用搜索的方法来完成，深度优先和广度优先
都行，广
度优先需要使用队列，稍微复杂一点，我这里就用深搜来完成。
1、输入数据，构造棋盘，总共三种颜色，0表示红色，1表示黄色，-1表示无
色；
2、从（1,1）点开始，往上下左右四个方向去搜索，这里和普通的只能往右和左
搜索的题目有点不
同，在普通的搜索里面，到达了一个点就设一个标志变量，然
后下次就不再搜索这个节点，但是这里不能
这么简单的处理，因为每个节点可以
往上下左右四个方向搜索，如果不设标志则会形成死循环，出不来，
设个标志则
有可能从不同的路径走到这个点的花费可能不相同，第一次的花费不一定是最低
的。
那么我们就把进到这个节点的花费记录下来，下次进入这个节点时候，比较
一下花费，如果相同或者大于
上次花费，就不用搜索这个节点，否则就继续搜索
他，我们把这种方法叫做记忆化搜索。
3、对于魔法问题，我们采用一点贪心策略，碰到一个无色格子，就让他变得和
当前格子颜色
一样，再到深搜递归函数里面加上一个参数，来表示魔法状态，如
果上次已经使用了魔法，而当前格子是
无色，也需要使用魔法，因为不能两次使
用魔法，就直接返回。
4、当走到了右下角（m,m
）点，说明已经找到了一条路径，把花费最小那条路
径记录下来就OK了。
这道题目还是比较简单的，具体看代码：
#include
#include
#include
using namespace std;
int
a[102][102],v[102][102],n,m,ans=999999;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};按右下左上搜索
搜索单元格（x,y），从（1,1）到上一单元已花费val
上个单元颜色为c，上单元是否使用魔法mo
void dfs(int x,
int y, int val, int c, bool mo)
{
if(a[x][y] == -1 && mo)不能两次魔法
return;
if(x==m&&y==m)
{
int temp=val;
if(a[m][m] != c)
{
temp++;
if(a[m][m]==-1)变魔法，在原来基础上再加1
temp++;
}
if(temp
ans=temp;
return;
}
if(a[x][y]==-1)
{
val
+= 2;
mo=1;
}
else
{
mo=0;
if(a[x][y] != c)
{
val += 1;
c=a[x][y];
}
}
if(val>=v[x][y] || val>=ans)
{
return;
}
else
{
v[x][y] =
val;
int xx,yy;
for(int i=0; i<4; i++)
{
xx=x+dx[i];
yy=y+dy[i];
if(xx>=1&&xx<=m&&yy>=1&&yy<=m)
dfs(xx,yy,val,c,mo);
}
}
}
int main()
{
int i, x, y, k;
cin>>m>>n;
memset(a, -1,
sizeof(a));把a数组全部设为-1表示没有颜色
memset(v,
127, sizeof(v));把v数组设为一个巨大的数字
for(i=0; i
{
scanf(
a[x][y] = k;
}
dfs(1,1,0,a[1][1],0);
if(ans==999999)
cout<<-1;
else
cout<
}