日常blog(✧◡✧)
算法：
然后这是2017普及组；
first.关于颜色处理：让c[i][j]=color+1；这样无色=0，红色=1，黄色=2；
然后其实是记忆化，将记答案的数组先初始化为一个很大的数（我初始为了0x3f3f3f3f）；
second.dfs主体部分：
1.四个变量：
x，y 存储搜索到的点的位置；
num 存储当前花费
used 存储是否使用过魔法；
2.几个返回的边界
①.当走出地图时，return；
②.当前搜到的值不如之前搜到的优（也包括相同的情况，如果不加相同的情况，重复的会反复搜），return；
③.当搜到最右下（m，m）时，先判断当前搜到的值是否优于之前的值（其实我赶脚不用判断qwq啊亲测不用）因为如果当前值不够优早在②就会被return；
所以如果能递归进判断的，一定更优，那么直接更新就好了；
3.真.主体部分：
1.向四个方向搜索（介里也是很像广搜了）
如果拓展后的节点有颜色，那么判断拓展的节点与当前节点的颜色是否相同
相同的话，花费就不需要增加，直接dfs（xx，yy，num，0）；
不同的话，花费需要加1，dfs（xx，yy，num+1，0）；
如果拓展节点没有颜色，那么判断当前节点是不是使用过魔法的点，如果是使用过魔法的点，那么显然走不下去了，如果未使用过魔法，就使用巴啦啦能量，把拓展节点变成与当前节点相同的颜色，dfs（xx，yy，num+2，1）；
最后不要忘记回溯：c[xx][yy]=0;
判断无解：
如果无解，ans的值就不会更新，为0x3f3f3f3f，如果dfs完，ans=0x3f3f3f3f，说明无解，否则有解，输出ans；
CODE：
#include<bits/stdc++.h> using namespace std; inline int read(){ int ans=0; char last=' ',ch=getchar(); while(ch>'9'||ch<'0') last=ch,ch=getchar(); while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar(); if(last=='-') ans=-ans; return ans; } int m,n; int c[101][101],a[101][101]; int ans=0x3f3f3f3f; int dx[5]={0,1,-1,0,0}; int dy[5]={0,0,0,1,-1}; void dfs(int x,int y,int num,int used){ if(x<1||y<1||y>m||x>m) return; if(num>=a[x][y]) return; a[x][y]=num; if(x==m&&y==m){ ans=num; return; } for(int i=1;i<=4;i++){ int xx=x+dx[i],yy=y+dy[i]; if(c[xx][yy]){//have color if(c[xx][yy]==c[x][y]) dfs(xx,yy,num,0); else dfs(xx,yy,num+1,0); } else { if(!used){ c[xx][yy]=c[x][y]; dfs(xx,yy,num+2,1); c[xx][yy]=0; } } } } int main(){ memset(a,63,sizeof(a)); m=read();n=read(); int x,y,color; for(int i=1;i<=n;i++){ x=read();y=read();color=read(); c[x][y]=color+1;//no color:0 //red color:1 yellow color:2 } dfs(1,1,0,0); if(ans==0x3f3f3f3f) printf("-1"); else printf("%d",ans); return 0; }
end-