%%%
by Luo_gu_fyh @ 2022-07-27 14:21:43
1. 采用优先队列,按每个格子最小代价排序;
```cpp
template<class T = int>
struct myNode {
T x,y,color,cost;
myNode(T newx,T newy,T newcolor,T newcost){x = newx; y = newy; color = newcolor; cost = newcost;}
myNode(const myNode& obj){ x = obj.x; y = obj.y; color = obj.color; cost = obj.cost;}
bool operator<( const myNode<T>& b) const
{
return cost > b.cost;
}
};
//template<class T>
//bool operator<(const myNode<T>& a,const myNode<T>& b) //此类操作符重载一定不能突变任何东西,并且两个操作数必须都是const
//{
// return a.cost > b.cost;
//}
priority_queue<myNode<int> > myque;//距离优先队列
```
2. BFS(int x,int y, int color ,int cost)
```cpp
void mybfs(int x,int y,int color,int cost) //无色格子在bfs是被更改为其父节点的颜色入队,原地图上的颜色不变
{
int currentx,currenty,currentcolor,currentcost;
if(mycolor[x][y] != -1)//每次bfs(x,y)时,根据原始地图mycolor(x,y)判断是否为有色格子
for(int i = 0; i < 4; ++i)
{
currentx = x + mydx[i];
currenty = y + mydy[i];
currentcolor = mycolor[currentx][currenty];
if(!myvis[currentx][currenty])
{
if((mycolor[currentx][currenty] == mycolor[x][y])) //将与x,y相临且颜色相同的格子，设置与(x,y)相同的cost
currentcost = cost;
else if(mycolor[currentx][currenty] != -1) //将与x,y相临且颜色相异的格子，cost设置(x,y)的cost+1
currentcost = cost + 1;
else//将与x,y相临且无色的格子，cost设置(x,y)的cost+2，颜色与(x,y)相同
{
currentcolor = color;
currentcost = cost + 2;
}
myvis[currentx][currenty] = 1;//设计计算标志,并入队
myque.push(myNode<int>(currentx,currenty,currentcolor,currentcost));
}
}
else //据原始地图mycolor(x,y)判断(x,y)为无色格子
{
for(int i = 0; i < 4; ++i) //检查(x,y)周围是否有未计算的有色格子,将其入队cost
{
currentx = x + mydx[i];
currenty = y + mydy[i];
if(!myvis[currentx][currenty] && mycolor[currentx][currenty] != -1)
{
if(mycolor[currentx][currenty] == color) //(x,y) 的临时颜色为color,相临的有色点与(x,y)临时同色
currentcost = cost;
else //与(x,y)相临的有色点,与(x,y)颜色不同
currentcost = cost + 1;
myvis[currentx][currenty] = 1;
myque.push(myNode<int>(currentx,currenty,mycolor[currentx][currenty],currentcost));
}
}
}
}
```
3. 主程序
```cpp
int main()
{
int m,n,ans;
memset(mycolor,-1,sizeof(mycolor));//初始每个格子为无色-1；
memset(myvis,0,sizeof(myvis)); //0表示没有被访问
cin >> m >> n;
for(int i = 1; i <= n; ++i) //读入有颜色的各个格子，并设置好颜色值
{
int x,y,color;
cin >> x >> y >> color;
mycolor[x][y] = color;
}
for(int i = 0; i <= m; ++i)//0列与0行的格子在棋盘之外,默认被计算过不可达
myvis[0][i] = myvis[i][0] = 1;
ans = -1;//默认目标不能到达
myvis[1][1] = 1;
myque.push(myNode<int>(1,1,mycolor[1][1],0));
while(!myque.empty())
{
myNode<int> tmp = myque.top() ;
myque.pop();
if(tmp.x == m && tmp.y == m) //到达目标
{
ans = tmp.cost;
break;
}
else
mybfs(tmp.x,tmp.y,tmp.color,tmp.cost);
}
cout << ans << endl;
return 0;
}
```
by lglwff @ 2022-07-28 00:10:23
明白了谢谢巨佬 @[lglwff](/user/30110)
by 流光剑客 @ 2022-07-31 18:52:55