题目链接：

思路：初始化step[][]==inf,然后如果当前点p.step<step[p.x][p.y],则入优先队列。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define inf 1<<30 8 struct Node{ 9    int x,y,step;10    bool operator < (const Node &p) const {11       return p.step
           
            Q;24 Node p,q;25 for(int i=1;i<=m;i++){26 p.x=1,p.y=i,p.step=1;27 Q.push(p);28 }29 while(!Q.empty()){30 p=Q.top();31 Q.pop();32 if(p.x==n)return p.step;33 for(int i=0;i<4;i++){34 q.x=p.x+dir[i][0];35 q.y=p.y+dir[i][1];36 q.step=p.step;37 if(q.x<1||q.x>n||q.y<1||q.y>m)continue;38 if(map[q.x][q.y]!=map[p.x][p.y])q.step++;39 if(Step[q.x][q.y]>q.step){40 Step[q.x][q.y]=q.step;41 Q.push(q);42 }43 }44 }45 return 1;46 }47 48 int main(){49 // freopen("1.txt","r",stdin);50 int _case;51 scanf("%d",&_case);52 while(_case--){53 scanf("%d%d",&n,&m);54 for(int i=1;i<=n;i++)55 scanf("%s",map[i]+1);56 int ans=bfs();57 printf("%d\n",ans);58 }59 return 0;60 }