记忆化广度优先搜索

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int map[105][105],val[105][105];//存数据，存到当前所花费的总数
struct node{
	int x,y,c,v;//坐标，上一个颜色，花费
};
queue<node>q;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int m,n,di[4][2]={0,1,1,0,0,-1,-1,0},ans=0x7f7f7f7f;
	memset(map,-1,sizeof(map));
	memset(val,0x7f,sizeof(val));
	cin>>m>>n;
	for(int i=0;i<n;i++){
		int x,y,c;
		cin>>x>>y>>c;
		map[x][y]=c;
	}
	q.push((node){1,1,map[1][1],0});
	val[1][1]=0;
	while(!q.empty()){
		int x=q.front().x,y=q.front().y,c=q.front().c,v=q.front().v;
		if(v>ans){//如果花费大于答案，跳过
			q.pop();
			continue;
		}
		if(x==m&&y==m){//找到目标，求最小
			ans=min(ans,v);
			q.pop();
			continue;
		}
		for(int k=0;k<4;k++){
			int dx=x+di[k][0],dy=y+di[k][1];
			if(dx>0&&dy>0&&dx<=m&&dy<=m){//未越界
				int bc=map[x][y],dc=map[dx][dy],mv=val[dx][dy],dv;//当前颜色，下一步颜色，下一步花费，总花费；
				if(dc>=0&&bc>=0){//都有颜色
					dv=v+(dc==bc?0:1);//是否相同
					if(mv>dv){
						q.push((node){dx,dy,dc,dv});//入队
						val[dx][dy]=dv;
					}
				}else if(dc<0&&bc>=0){//下一步无色，当前有色
					if(mv>v+2){
						q.push((node){dx,dy,bc,v+2});//加入的是当前颜色，因为用了魔法
						val[dx][dy]=v+2;
					}
				}else if(dc>=0&&bc<0){//下一步有色，当前无色，查看是否相同
					dv=v+(c==dc?0:1);//现在的颜色和之前是否相等
					if(mv>dv){
						q.push((node){dx,dy,dc,dv});
						val[dx][dy]=dv;
					}
				}
			}
		}
		q.pop();
	}
	if(ans==0x7f7f7f7f){
		cout<<"-1"<<endl;
	}else {
		cout<<ans<<endl;
	}
	return 0;
}