你只记录了一种状态（当前搜到的点的坐标），但是其实没完
由于染色的存在，还要**记录当前是否染过色**。
而由于染色只能染一次，还要**记录当前染了什么色**，如：
A点黄色，B点白色（无色），C点红色。那么从A到B变为（Xb,Yb,染过色,染了黄色），此时再想从B到C是不可能的了，但是你的源代码可以。
所以要开四维，两维表示坐标，一维**表示是否可以染色**，一维**表示染了什么色**，方便接下来的搜索（ _刚才的C如果是红色就可以走_ ）
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,lrj,dis[103][103][6][2],a[103][103],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
struct node{
int x,y,c,can,s;
bool operator<(const node bb)const{
return s>bb.s;
}
}t;
bool fg[103][103][6][2];
priority_queue<node> q;
inline node make_n(int x,int y,int c,int can,int s)
{
node qwq;
qwq.x=x;
qwq.y=y;
qwq.c=c;
qwq.can=can;
qwq.s=s;
return qwq;
}
signed main()
{
cin>>n>>lrj;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=0;k<4;k++)
{
dis[i][j][k][0]=dis[i][j][k][1]=1e9;
fg[i][j][k][0]=fg[i][j][k][1]=0;
}
}
}
for(int x,y,c;lrj--;)
{
cin>>x>>y>>c;
c++;
a[x][y]=c;
}
dis[1][1][a[1][1]][1]=0;
q.push(make_n(1,1,a[1][1],1,0));
int x,y,c,op;
do{
t=q.top();
q.pop();
x=t.x;
y=t.y;
c=t.c;
op=t.can;
if(fg[x][y][c][op])
{
continue;
}
fg[x][y][c][op]=1;
for(int i=0,tx,ty;i<4;i++)
{
tx=x+dx[i];
ty=y+dy[i];
if(tx>=1&&ty>=1&&tx<=n&&ty<=n)
{
if(a[tx][ty]==c)
{
if(dis[tx][ty][c][1]>dis[x][y][c][op])
{
dis[tx][ty][c][1]=dis[x][y][c][op];
q.push(make_n(tx,ty,c,1,dis[tx][ty][c][1]));
}
}
else
{
if(a[tx][ty])
{
if(dis[tx][ty][a[tx][ty]][1]>dis[x][y][c][op]+1)
{
dis[tx][ty][a[tx][ty]][1]=dis[x][y][c][op]+1;
q.push(make_n(tx,ty,a[tx][ty],1,dis[tx][ty][a[tx][ty]][1]));
}
}
else
{
if(op)
{
if(dis[tx][ty][a[x][y]][0]>dis[x][y][c][op]+2)
{
dis[tx][ty][a[x][y]][0]=dis[x][y][c][op]+2;
q.push(make_n(tx,ty,a[x][y],0,dis[tx][ty][a[x][y]][0]));
}
}
}
}
}
}
}while(q.empty()==0);
if(a[n][n])
{
if(min(dis[n][n][a[n][n]][0],dis[n][n][a[n][n]][1])==1e9)
{
puts("-1");
}
else
{
cout<<min(dis[n][n][a[n][n]][0],dis[n][n][a[n][n]][1]);
}
}
else
{
int ans=1e9;
for(int k=0;k<4;k++)
{
//cout<<dis[n][n][k][0]<<" "<<dis[n][n][k][1]<<"\n";
ans=min(ans,min(dis[n][n][k][0],dis[n][n][k][1]));
}
if(ans==1e9)
{
puts("-1");
}
else
{
cout<<ans;
}
}
return 0;
}
```
~~仅供参考，我不是广搜而是dijkstra~~
by wjy959 @ 2023-09-14 21:49:11