1.6.4 棋盘问题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<stdio.h>
-
#include<algorithm>
-
-
//本代码可以把所有vis删去，不影响运行结果
-
//本代码可以把所有vis删去，不影响运行结果
-
//本代码可以把所有vis删去，不影响运行结果
-
-
int m,n;//棋盘大小，有色格子
-
int map[101][101];//棋盘数据
-
int step[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//移动方向
-
int ans=0xFFFFFFF;//答案，花费最少金币数
-
int d[101][101];//到达某个格子花费的最少金币数
-
int vis[101][101];//标记走过的格子
-
-
//横、纵坐标，是否使用过魔法，花费金币总数
-
void dfs(int x,int y,bool magic,int sum)
-
{//如果这次走到(x,y)花的金币不比之前搜索的少，必定不是最优解
-
if(sum>=d[x][y]) return;
-
//否则更新最优解
-
d[x][y]=sum;
-
-
//判断是否到终点，是则更新答案
-
if(x==m && y==m){
-
ans=std::min(sum,ans);
-
return;
-
}
-
//否则开始枚举往四个方向走
-
int X,Y;
-
for(int i=0;i<4;i++)
-
{//计算下个格子坐标
-
X=x+step[i][0];
-
Y=y+step[i][1];
-
-
//判断下标越界，判断重复访问
-
if(X<1||X>m||Y<1||Y>m||vis[X][Y]) continue;
-
-
//如果是空格
-
if(map[X][Y]==2){
-
//如果上次使用过魔法，此路不通
-
if(magic) continue;
-
else {//上次没用魔法，可以用
-
vis[X][Y]=true;//标记
-
//因为要花最少金币，所以指定颜色和过来的格子一样
-
map[X][Y]=map[x][y];
-
dfs(X,Y,true,sum+2);//走到下一个格子上
-
map[X][Y]=2;//恢复空白
-
}
-
}
-
//如果不是空格
-
else if(map[X][Y]!=2){
-
vis[X][Y]=true;//标记
-
if(map[x][y]==map[X][Y]){//颜色相同
-
dfs(X,Y,false,sum);
-
}
-
else dfs(X,Y,false,sum+1);//颜色不同
-
}
-
//回溯
-
vis[X][Y]=false;
-
}
-
return;
-
}
-
-
int main()
-
{//初始化
-
for(int i=0;i<101;i++)
-
{
-
for(int j=0;j<101;j++)
-
{
-
map[i][j]=2;//全是空格
-
d[i][j]=0xFFFFFFF;//全是最大值
-
vis[i][j]=false;//全是未访问
-
}
-
}
-
-
scanf("%d%d",&m,&n);
-
int x,y;
-
while(n)
-
{//给指定格子涂色
-
scanf("%d%d",&x,&y);
-
scanf("%d",&map[x][y]);
-
--n;
-
}
-
-
vis[1][1]=true;//先行标记起点
-
dfs(1,1,false,0);//传初态
-
-
if(ans!=0xFFFFFFF) printf("%d",ans);//如果有解
-
else printf("-1");//如果无解
-
-
return 0;
-
}
文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/weixin_54227557/article/details/120607510
- 点赞
- 收藏
- 关注作者
评论（0）