[NOIP2017 普及组] 棋盘——深搜 详解

题目背景

NOIP2017 普及组 T3

题目描述

有一个 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?枚金币。

共花费?88?枚金币。

样例 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。

对于?1100%?的数据，1≤m≤100,1≤n≤1,000。

分析

深度优先搜索算法

代码具体分析

1.头文件和命名空间

使用了万能头文件，包含了所有的标准库头文件，方便编写代码。

同时使用了命名空间std，避免了重名问题。

2.变量解释

二维数组a和v，分别表示迷宫的颜色和每个格子到起点的最小金币花费

dir数组，表示四个方向的移动

m和n，分别表示迷宫的大小和颜色变化的数量

ans，表示到达终点的最小金币花费，初始化为一个很大的数

3.深度优先搜索

这里使用了深度优先搜索算法

• 从起点开始搜索，每次尝试往上下左右四个方向走到下一个格子。
• 如果下一个格子是无色，则花费2个金币改变颜色；如果下一个格子是有色，则花费1个金币改变颜色
• 如果颜色和上一个格子不同，则花费1个金币。
• 如果下一个格子是终点，则判断最后一个格子的颜色是否和上一个格子的颜色不同，如果不同，则花费1个金币
• 如果当前金币花费已经大于等于到达该格子的最小金币花费或者大于等于到达终点的最小金币花费，则剪枝。否则，更新到达该格子的最小金币花费，并继续搜索下一个格子。

4.主函数

首先输入迷宫的大小和颜色变化的数量，然后初始化a数组为-1，表示刚开始都是无色

初始化v数组为一个很大的数，表示到达每个格子的最小金币花费

接着输入每个格子的颜色，更新a数组

最后调用dfs函数，从起点开始搜索。如果到达终点的最小金币花费为一个很大的数，则输出-1，否则输出到达终点的最小金币花费

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N],v[N][N];
int dir[4][2]={-1,0,0,1,1,0,0,-1}; 
int m,n,ans=0x3f3f3f3f;
//搜索单元格是(x,y),从(1,1)到达(x,y)已用到的金币数量是val
//(x,y)的上一个单元格的颜色是c，(x,y)的上一单元是否使用了魔法 
void dfs(int x,int y,int val,int c,int mo){
	if(a[x][y]==-1&&mo) return;//不能连续使用魔法
	if(x==m&&y==m){//到达终点 
		if(a[m][m]!=c){//最后一个和上一个颜色不一样 
			val++;
			if(a[m][m]==-1) val++; 
		} 
		if(val<ans)  ans=val;
		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;//记忆化 
		for(int i=0;i<4;i++){
			int xx=x+dir[i][0],yy=y+dir[i][1];
			if(xx>=1&&xx<=m&&yy>=1&&yy<=m)
				dfs(xx,yy,val,c,mo);
		}
	}
}
int main(){
	cin>>m>>n;
	memset(a,-1,sizeof a);//-1表示刚开始都是无色 
	memset(v,0x3f,sizeof v);
	int x,y,k;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>k;
		a[x][y]=k;//(x,y)的颜色是k 
	}
	dfs(1,1,0,a[1][1],0); 
	if(ans==0x3f3f3f3f) cout<<-1;
	else cout<<ans;
	return 0;
}