SP22393 KATHTHI 题解

题目链接：SP22393 KATHTHI

题意：

多组数据。每组数据给定一个 \(n\times m\) 的方格，每个格子里有一个小写字母。

每次移动操作可以移到四连通的格子内。如果目标格子的字母与当前格子相同，则花费 \(0\) ，否则花费 \(1\) 。

求 \((1,1)\) 到 \((n,m)\) 的最小花费。

显然是 01bfs ，不知道怎么标的蓝。

对于网格上的最短路，我们一般把它直接看成图，也就是网格图。

由于边权只有 0 或 1 ，所以我们可以用 01bfs ，也就是用一个双端队列维护 bfs 。

如果当前移动没有消耗，则我们把它放到队头，再次移动。这样可以保证每次先跑的一定是优的。

时间复杂度 \(\mathcal{O}(\sum nm)\)

代码：（题解区随便扒的）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>
#define ll long long
#define rgt register int
#define pir pair<int,int>
using namespace std;
const int mxn = 1111;

char mp[mxn][mxn];  //存储字符网络
int n,m,lz,f[mxn][mxn];  //f[i][j]存储到达点(i,j)的最小代价
int px[4]={-1,1,0,0};
int py[4]={0,0,-1,1}; 
pir g;
struct que_mode{
	int x;
	int y;
	char c;
}z[mxn*mxn],to;  //记录点坐标和当前点的字符

int main(){

	int test,sg;
	char ch;
	scanf("%d",&test);  //读入测试数据组数
    
	while(test--){
    
		scanf("%d%d",&n,&m);
		for(rgt i=1;i<=n;i++){
			scanf("%c",&ch);
			for(rgt j=1;j<=m;j++){
				scanf("%c",&mp[i][j]);
			}
		} //读入字符网络
        
		memset(f,127,sizeof(f));
		deque <pir> que;
		lz=1;
		z[lz].x=1;
		z[lz].y=1;
		z[lz].c=mp[1][1];
		f[1][1]=0;
		que.push_front(make_pair(0,1));
                //建双端队列并初始化
        
		while(!que.empty()){
        
			g=que.front();  //取出队首
			que.pop_front();  //删除队首
            
			if(z[g.second].x==n&&z[g.second].y==m)
				break;
                        //如果已经到达终点(n,m)，证明找到最优方案，跳出循环
                
			for(rgt i=0;i<4;i++){
				to.x=z[g.second].x+px[i];
				to.y=z[g.second].y+py[i];
                                //生成新的点坐标
                
				if(to.x>=1&&to.x<=n&&to.y>=1&&to.y<=m){  //判断是否越界
                
					to.c=mp[to.x][to.y];
					sg=to.c==z[g.second].c?g.first:g.first+1;  //计算转移需要的代价
                    
					if(sg<f[to.x][to.y]){  //如果可以更新代价
						lz++;
						z[lz]=to;  //存储点坐标
						f[to.x][to.y]=sg;  //更新最优方案
						if(to.c==z[g.second].c)   //入队
							que.push_front(make_pair(sg,lz));
						else
							que.push_back(make_pair(sg,lz));
					}
				}
			}
		}
		printf("%d\n",f[n][m]);  //输出答案
	}
	return 0;
}