题目描述：https://www.acwing.com/problem/content/473/
题目具体内容：
　　有一个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≤m≤100,
　　1≤n≤1000
【输入样例】：
　　5 7
　　1 1 0
　　1 2 0
　　2 2 1
　　3 3 1
　　3 4 0
　　4 4 1
　　5 5 0
【输出样例】：
　　8
分析：这个题目题面比较好理解，在训练的基本平面格子上的搜索上做了一些变型，除了成上下左右走之外，还需要根据相邻格子间的颜色来决定是否能走，如果能走，走下去将会产生的金币数要维护最小值。求从格子左上到右下的最少花费金币数。
搜索可以采用宽搜和深搜，在搜索时记录当前所产生的金币数。
具体代码如下：
【宽搜BFS写法】

#include<bits/stdc++.h>
using namespace std;

struct sts{
	int x,y,nowcolor,step;
};
int chess[100+6][100+6]; //存储从左上走到当前格子上时的最少金币数 
int chcol[106][106];  //存储格子上的颜色值，-1代表透明，0代表红色，1代表黄色 
queue<sts>q;    //宽搜需要用到的队列STL 
const int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1}; 
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	memset(chess,0x3f,sizeof(chess));
	memset(chcol,-1,sizeof(chcol));
	for (int i = 1;i <= n; i++){
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		chcol[x][y] = c;   //0代表红色，1代表黄色
	}
	q.push((sts){1,1,chcol[1][1],0});
	chess[1][1] =0;
	while(!q.empty()){
		sts t = q.front();
		q.pop();		
		for(int i = 1 ;i<= 4; i++){
			int newx = t.x + dx[i];
			int newy = t.y + dy[i];
			int nowcolor = chcol[newx][newy];
			if(newx < 1 || newx > m || newy < 1 || newy > m) continue;	
			//计算金币数 
			int money = 0;	
			if(chcol[t.x][t.y] == -1){
				if(chcol[newx][newy] == -1) money = -1;
				else if(t.nowcolor == chcol[newx][newy]) money = 0;
				else money = 1;
			}
			else{
				if(chcol[newx][newy] == -1) money = 2,nowcolor = chcol[t.x][t.y];
				else if(chcol[t.x][t.y] == chcol[newx][newy]) money = 0;
				else money = 1;
			}
			//如果能走，在走下来的金币数更少时更新走到该格子的最少金币数，并入队列。 
			if(money != -1 && chess[newx][newy]> t.step+ money){
				chess[newx][newy] = t.step + money;
				q.push((sts){newx,newy,nowcolor,chess[newx][newy]});			
			}
		}
	}
	if(chess[m][m] == 0x3f3f3f3f) chess[m][m] = -1;
	printf("%d",chess[m][m]);
	return 0;
} 

【深搜DFS写法】

#include<bits/stdc++.h>
using namespace std;

int chess[100+6][100+6];
int chcol[106][106];
int is_ov[105][105];
int ans = 0x3f3f3f3f;
int m,n;
const int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1}; 

void dfs(int x,int y,int step,int lastcol){
	if(chess[x][y] <= step) return;   //记忆化 
	chess[x][y] = step;
	for(int i = 1;i<= 4;i++){
		int newx = x + dx[i], newy = y + dy[i];
		if(newx < 1 || newx > m || newy < 1 || newy > m) continue;	
		//计算金币数。 
		int money = 0;	
		if(chcol[x][y] == -1){
			if(chcol[newx][newy] == -1) money = -1;
			else if(lastcol == chcol[newx][newy]) money = 0;
			else money = 1;
		}
		else{
			if(chcol[newx][newy] == -1) money = 2;
			else if(chcol[x][y] == chcol[newx][newy]) money = 0;
			else money = 1;
		}
		//能继续往下走的，则继续搜索。 
		if(money != -1 ) {	
		    if(money == 2)	dfs(newx,newy,step+money, chcol[x][y]); 
		    else dfs(newx,newy,step+money, chcol[newx][newy]); 
		}
	}
}
int main(){
	
	scanf("%d%d",&m,&n);
	memset(chess,0x3f,sizeof(chess));
	memset(chcol,-1,sizeof(chcol));
	for (int i = 1;i <= n; i++){
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		chcol[x][y] = c;   //0代表红色，1代表黄色
	}
	dfs(1,1,0,0); 
	if(chess[m][m] == 0x3f3f3f3f) chess[m][m] = -1;
	printf("%d",chess[m][m]);
	return 0;
}