我觉得很神奇，双端队列BFS/01BFS每次进行的选择究竟是不是一定最优。

有3个题目：P1849 P4162 SP22393

前两题都可以用类似于下面这段代码的代码来过：

//File: P1849.cpp
//Author: yanyanlongxia
//Date: 2020/8/5
//[USACO12MAR]Tractor S
//双端队列写的01BFS更好看，而且代码更短……
#include <bits/stdc++.h>
#define MN 1100
using namespace std;
const int dx[4]={-1,0,0,1},dy[4]={0,1,-1,0};
int n,step[MN][MN];
bool ih[MN][MN];
pair<int,int>st;
deque<pair<int,int>>q;
int main() {
    int x,y;
    memset(step,-1,sizeof(step));
    scanf("%d%d%d",&n,&st.first,&st.second);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        ih[x][y]=true;
    }
    step[st.first][st.second]=0;
    q.push_front(st);
    while(!q.empty())
    {
        pair<int,int> now=q.front();
        q.pop_front();
        for(int i=0;i<4;i++)
        {
            pair<int,int>nxt=make_pair(now.first+dx[i],now.second+dy[i]);
            if (nxt.first<0 || nxt.first>MN || nxt.second<0 || nxt.second>MN)
                continue;
            if(step[nxt.first][nxt.second]!=-1)
                continue;
            if(ih[nxt.first][nxt.second])
            {
                step[nxt.first][nxt.second]=step[now.first][now.second]+1;
                q.push_back(nxt);
            } else{
                step[nxt.first][nxt.second]=step[now.first][now.second];
                q.push_front(nxt);
            }
        }
    }
    printf("%d\n",step[0][0]);
    return 0;
}

注意这宽搜里面当扩展到里面时，没有考虑是否存在比当前更优的情况，直接扩展，顺便做上标记，防止再次扩展到当前点。

而第三题，我也这么写了，却WA了，连样例都没过，但是加上松弛的部分就AC了。

这是我的第三题的正确代码：

//File: test.cpp
//Author: yanyanlongxia
//Date: 2020/8/5
//
#include <bits/stdc++.h>
using namespace std;
const int dx[4]={-1,0,0,1},dy[4]={0,1,-1,0};
int t,n,m,step[1005][1050];
char s[1005][1005];
deque< pair<int,int> >q;
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(step, 0x3f3f3f3f, sizeof(step));
        q.clear();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%s", (s[i] + 1));
        step[1][1] = 0;
        q.push_front(make_pair(1, 1));
        while (!q.empty()) {
            pair<int, int> now = q.front();
            q.pop_front();
            for (int i = 0; i < 4; i++) {
                int x = now.first + dx[i], y = now.second + dy[i];
                if (x < 1 || y < 1 || x > n || y > m)
                    continue;
                if (s[now.first][now.second] == s[x][y]&&step[now.first][now.second] < step[x][y]) {
                    step[x][y] = step[now.first][now.second];
                    q.push_front(make_pair(x, y));
                } else {
                    if(step[now.first][now.second]+1 < step[x][y])
                    {
                        step[x][y] = step[now.first][now.second] + 1;
                        q.push_back(make_pair(x, y));
                    }

                }
            }
        }
        printf("%d\n", step[n][m]);
    }
    return 0;
}

我觉得这三题非常相似，可是为什么前两题中的做法第三题中不行呢？还是第三题和前两题有什么本质上的不同？请问大佬们可以回答一下这个问题吗？