SP22393 KATHTHI - KATHTHI
题目大意：
给定一个 \(n \times m\) 的网格，每个位置有一个小写字母，每次可以上下左右走，如果 \(s[x][y]=s[nx][ny]\) 则这步花费为 \(0\) ，否则为 \(1\) 。求从 \((1,1)\) 到 \((n,m)\) 的最小花费。
solution:
翻译的题面非常友善，给了一句话
`提示：不要用某些“活着”的最短路算法`
所以我们考虑其他最短路的方法，我们可以用 \(\text{BFS}\) 来求最短路。但普通的 \(\text{BFS}\) 时间复杂度爆炸。考虑优化，发现在 \(\text{BFS}\) 的队列中，取出队头并不能确保它是最优的。所以一种新的方法出现了——双端队列 \(\text{BFS}\) \((\text{deque}+\text{BFS})\) ,这样我们能保证，任意时刻广搜队列中节点对应的距离值都有“两端性”和“单调性”，每个节点第一次被访问时，就能得到最短距离。
正确性证明：
由于我们最终目标是求路径权值和，而权值为\(0\)的边无论走多少条权值和依旧是 \(+0\) ，因此我们可以优先走权值为 \(0\) 的边，更新与这些边相连的点 \(x\) 的 \(d[x]\)（ \(d[i]\) 为从 \(s\) 到 \(i\) 最小权值和），此时 \(d[x]\) 一定是最小的，因为它是由尽可能多的权值为0的边更新而来。所以在队列中取出的节点同时满足“连通性”和“权值最小”，因此每个节点仅需被更新一次。（引自CSDNhttps://valen.blog.csdn.net/）
接下来是细节的处理：
- 多组输入记得 \(dis\) 要初始化(较大值 \(0x3f3f3f3f\) )
看到这的同学，可以自己去写代码了(tf口吻)
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
const int N=1005;
int n,m;
char s[N][N];
int dx[5]={0,-1,0,1};
int dy[5]={1,0,-1,0};
int dis[N][N];
struct D{int x,y,c;};
void bfs()
{
deque<D> q;
D now;
now.x=0,now.y=0,now.c=0;
q.push_front(now);
dis[0][0]=0;
while(q.size())
{
int x=q.front().x,y=q.front().y,c=q.front().c;
q.pop_front();
if(x==n-1&&y==m-1) break;
for(int i=0;i<4;i++)
{
int zx=x+dx[i],zy=y+dy[i];
if(zx<0||zx>=n||zy<0||zy>=m) continue;
if(s[x][y]==s[zx][zy]&&c<dis[zx][zy])
{
dis[zx][zy]=c;
D now;
now.x=zx,now.y=zy,now.c=c;
q.push_front(now);
}
else if(s[zx][zy]!=s[x][y]&&c+1<dis[zx][zy])
{
dis[zx][zy]=c+1;
D now;
now.x=zx,now.y=zy,now.c=c+1;
q.push_back(now);
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",s[i]);
bfs();
printf("%d\n",dis[n-1][m-1]);
}
return 0;
}