#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[110][110];
int vis[110][110];
int f[110][110];
int res = 0x3f3f3f3f;
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};
void dfs(int x, int y, int col, int coat){
if(coat >= f[x][y])return;
f[x][y] = coat;
if(x == m && y == m){
res = min(res,coat);
return;
}
vis[x][y] = 1;
for(int i=0;i<4;i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx>=1 && xx<=m && yy>=1 && yy<=m && !vis[xx][yy]){
if(col == a[xx][yy]){
dfs(xx,yy,a[xx][yy],coat);
}else if(col != a[xx][yy]){
if(a[xx][yy] == 0 && col == a[x][y]){
dfs(xx,yy,col,coat+2);
}else if(a[xx][yy] != 0){
dfs(xx,yy,a[xx][yy],coat+1);
}
}
}
}
vis[x][y] = 0;
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
int x,y,c;
cin>>x>>y>>c;
a[x][y] = c+1;
}
memset(f,127,sizeof f);
dfs(1,1,a[1][1],0);
if(res == 0x3f3f3f3f){
puts("-1");
}else{
printf("%d",res);
}
}本质上来说并不是特别复杂的搜索，只不过这个搜索时要维护多个状态量，没怎么做过属于是文章来源：https://www.toymoban.com/news/detail-536358.html
同时有一个剪枝就是维护走到 （i，j）的最短花费，大于这个花费就直接减掉文章来源地址https://www.toymoban.com/news/detail-536358.html
到了这里，关于P3956棋盘 ( dfs + 剪枝的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
