bfs + deque

利用双端队列加速bfs的过程

P4554 小明的游戏

题目描述
小明最近喜欢玩一个游戏。给定一个n*m的棋盘，上面有两种格子#和@。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是0，否则费用是1。请编程计算从起始位置移动到目标位置的最小花费。
输入格式
输入文件有多组数据。
输入第一行包含两个整数n，m，分别表示棋盘的行数和列数。
输入接下来的nn行，每一行有m个格子（使用#或者@表示）。
输入接下来一行有四个整数x1,y1,x2,y2，分别为起始位置和目标位置。
当输入n，m均为0时，表示输入结束。
输入

2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0

输出

2
0

实现
bfs广搜
我们在用dijkstra跑最短路的时候，会用到堆优化，把当前最短路最小的点放到前面去。
现在这个图的权要么是0，要么是1，如果还用堆来维护，似乎有些浪费了。
这个时候我们就要用到双端队列，它支持查询队头、队尾，加入元素到队头、队尾。
我们仍然希望距离大的点放后面，小的放前面，该怎么办呢？
因为只有0和1两种权值，如果u→v的边是0权，那就把v放在队头；否则放在队尾。
现在原本\(\Theta(\log n)\)的堆优化，在这里只需要\(\Theta(1)\)了！
deque
代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;
typedef long long ll;
const int N=2e3;
struct node{
   int x;
   int y;
};
char c[N][N],s;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int dis[N][N];
int n,m,x1,x2,y1,y2;
bool vis[N][N];
void bfs()
{
    deque<node> q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[x1][y1] = 0;
    q.push_back((node){x1,y1});
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        q.pop_front();
        if(vis[x][y]) continue;
        vis[x][y] = true;
        for(int i=0;i<=3;i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
            int w;
            if(c[tx][ty] == c[x][y]) w = 0;
            else w = 1;
            if(dis[tx][ty] < dis[x][y] + w) continue;
            dis[tx][ty] = dis[x][y] + w;
            if(w == 0) q.push_front((node){tx,ty});
            else q.push_back((node){tx,ty});

        }
    }
}
int main()
{
    while(1)
    {
        cin>>n>>m;
        if(n == 0 && m == 0) break;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
        }
        cin>>x1>>y1>>x2>>y2;
        x1++;y1++;x2++;y2++;
        bfs();
        printf("%d\n",dis[x2][y2]);
    }
    return 0;
}