一道有趣的搜索题......

测试样例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

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+5;
typedef long long ll;
ll inf = 0x3f3f3f3f;//最大值 
int m,n;
ll minu=inf;
int a[N][N];//原始棋盘 
ll dis[N][N];//记忆化 
bool vis[N][N];//标记回溯 int mx[]={-1,1,0,0};
int my[]={0,0,-1,1};bool inmap(int x,int y)
{return x>=1&&x<=m&&y>=1&&y<=m;
}void dfs(int x,int y,ll s,bool flag)
{if(s>inf) return;if(x==m && y==m){minu=min(minu,s);return;}for(int i=0;i<4;i++){int dx=x+mx[i],dy=y+my[i];if(!vis[dx][dy] && inmap(dx,dy)){vis[dx][dy]=1;//有颜色 if(a[dx][dy] != -1){//颜色相同if(a[dx][dy]==a[x][y] && dis[dx][dy] > s){dis[dx][dy] = s;dfs(dx,dy,s,0);}else//颜色不同 {if(dis[dx][dy] > s + 1){dis[dx][dy] = s + 1;dfs(dx,dy,s + 1,0);}	}}else if(a[dx][dy] == -1 && !flag)//没有颜色 {a[dx][dy] = a[x][y];if(dis[dx][dy] > s + 2){dis[dx][dy] = s + 2;dfs(dx,dy,s + 2,1); }		a[dx][dy] = -1;}vis[dx][dy]=0;}}
}int main()
{ios::sync_with_stdio(false);memset(a,-1,sizeof(a));memset(dis,0x3f,sizeof(dis));cin>>m>>n;for(int i=1;i<=n;i++){int x,y,clor;cin>>x>>y>>clor;a[x][y]=clor;}dfs(1,1,0,0);if(minu!=inf)cout<<minu<<endl;else cout<<-1<<endl;return 0;
}