双端队列模BFS模型

小明的游戏

tip

一个棋盘，从初始点走到终点，棋盘坐标中有两个符号。上下左右四个方向走，如果当前的符号和要走到的位置符号一样的话，不花费；如果不一样，花费1。求从起点到终点的最小花费。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;

typedef pair<int, int> PII;


const int N = 510;
char g[N][N];
int n,m;
int sx,sy,tx,ty;
bool st[N][N];
int dist[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs()
{
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);
    deque<PII> dq;
    dq.push_front({sx,sy});
    dist[sx][sy] = 0;
    while (dq.size())
    {
        auto t = dq.front();
        dq.pop_front();
        int x = t.first, y = t.second;
        if(st[x][y]) continue;
        st[x][y] = true;
        for(int i = 0;i < 4;i++)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if(nx >= 0 and nx < n and ny >= 0 and ny < m)
            {
                int w = g[x][y] != g[nx][ny];
                if(dist[nx][ny] > dist[x][y] + w)
                {
                    dist[nx][ny] = dist[x][y] + w;
                    if(w) dq.push_back({nx,ny});
                    else dq.push_front({nx,ny});
                }
            }
        }
    }
    
}

int main()
{
    freopen("1.txt","r",stdin);
    while(1)
    {
        cin >> n >> m;
        if(n == 0 and m == 0) break;
        for(int i = 0;i < n;i ++)
            cin >> g[i];
        cin >> sx >> sy >> tx >> ty;
        bfs();
        cout << dist[tx][ty] << endl;
    }    
}

Labyrinth

tip

走迷宫，给出一个起点。规定只能往左走l步，往右走r步，往上和往下任意走。求能够到达的位置的个数。

这个题也能用01bfs来做！往上走和往下走的话，花费为0，更新节点放到队首，要尽量往上走和往下走。往左和往右走，更新节点放队尾，有花费，少用！跑一遍bfs就行了。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 2010;
int n,m;
int sx,sy;
int lCnt,rCnt;
int cnt;    

char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct Node
{
    int x,y,l,r;
};

void bfs()
{
    deque<Node> dq;
    dq.push_back({sx,sy,lCnt,rCnt});
    // cnt ++;
    while(dq.size())
    {
        auto t = dq.front();
        dq.pop_front();
        int x = t.x,y = t.y;
        int l = t.l, r = t.r;
        for(int i = 0;i < 4;i++)
        {   
            int nx = x + dx[i],ny = y + dy[i];
            if(nx < 1 or nx > n or ny < 1 or ny > m or g[nx][ny] == '*') continue;
            if(i == 1)
            {
                if(!r) continue;
                dq.push_back({nx,ny,l,r-1});
            }else if(i == 3)
            {
                if(!l) continue;
                dq.push_back({nx,ny,l-1,r});
            }else if(i == 0 or i == 2) dq.push_front({nx,ny,l,r});
            cnt++;
            g[nx][ny] = '*';
        }   
    }
}


int main()
{
    freopen("1.txt","r",stdin);
    cin >> n >> m >> sx >> sy >> lCnt >> rCnt;
    for (int i = 1; i <= n; i ++ )
        for(int j = 1;j <= m;j ++)
            cin >> g[i][j];
    bfs();
    cout << cnt;
    return 0;
}

拖拉机

tip

大致题意：农夫在麦田里，麦田里有许多稻草堆，问最小需要移除多少稻草堆才能回到原点

思路：使用双端队列BFS求解，有稻草堆的权重是1，没有稻草堆的权重是0

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;


const int N = 1010;
int g[N][N];
int dist[N][N];
bool st[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n;
int sx,sy;

void dfs()
{
    memset(dist,0x3f,sizeof dist);
    deque<PII> dq;
    dq.push_back({sx,sy});
    dist[sx][sy] = 0;
    while(dq.size())
    {
        auto t = dq.front();
        dq.pop_front();
        int x = t.first,y = t.second;
        if(st[x][y]) continue;
        st[x][y] = true;
        for(int i = 0;i < 4;i++)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if(nx < 0 or nx > 1010 or ny < 0 or ny > 1010) continue;
            int w = g[nx][ny];
            if(dist[nx][ny] > dist[x][y] + w)
            {
                dist[nx][ny] = dist[x][y] + w;
                if(w) dq.push_back({nx,ny});
                else dq.push_front({nx,ny});
            }
        }
    }
}


int main()
{
    cin >> n >> sx >> sy;
    for (int i = 0; i < n; i ++ )
    {
        int x,y;
        cin >> x >> y;
        g[x][y] = 1;
    }
    dfs();
    cout << dist[1][1];
}