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

#include

//本代码可以把所有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;

}

视频接入服务 VIS

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。