01 bfs

UVA11573 Ocean Currents

分析：
题中给了两种移动方式，一种是沿着洋流的方向移动，不需要消耗能量，不沿着洋流走需要消耗1能量，此类按照普通的bfs不能保证队列前面的一定是当前消耗能量最少的情况。
正确做法是利用双端队列，不消耗能量就从队首入队，消耗能量就从队尾入队，这样就能保证队列前面的一定是当前消耗能量最小的
AC代码：

#include <bits/stdc++.h>

using namespace std;

int n, m;
char ch[1005][1005];
int ans;
int k;
int rs, cs, rd, cd;
struct node
{
    int x, y, t;
};
int vis[1005][1005];
int mov[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

bool judge(struct node no)
{
    if(no.x < 1 || no.x > n || no.y < 1 || no.y > n)    return true;
    return false;
}

void bfs(int rs, int cs, int rd, int cd)
{
    memset(vis, 0x3f3f, sizeof(vis));
    ans = 0;
    deque<node> q;
    node now, next;
    vis[rs][cs] = 0;
    now.x = rs, now.y = cs, now.t = 0;
    q.push_front(now);

    while(!q.empty())
    {
        now = q.front();
        q.pop_front();
        if(now.x == rd && now.y == cd)
        {
            ans = now.t;
            return ;
        }
        for(int i = 0; i < 8; ++i)
        {
            next.x = now.x + mov[i][0];
            next.y = now.y + mov[i][1];
            if(judge(next)) continue;
            if(ch[now.x][now.y] - '0' == i)
            {
                next.t = now.t;
                if(vis[next.x][next.y] > next.t)
                {
                    vis[next.x][next.y] = next.t;
                    q.push_front(next);
                }
            }
            else
            {
                next.t = now.t + 1;
                if(vis[next.x][next.y] > next.t)
                {
                    vis[next.x][next.y] = next.t;
                    q.push_back(next);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%s", ch[i] + 1);
    scanf("%d", &k);
    while(k--)
    {
        scanf("%d%d%d%d", &rs, &cs, &rd, &cd);
        bfs(rs, cs, rd, cd);
        printf("%d\n", ans);
    }
    return 0;
}

CF590C Three States

分析：
这个题与和上一个不同于不是单一起点和单一终点
这个题需要以每个国家的任意一格为起点，对整张图跑一遍01BFS，就得到了三个国家到所有各自的距离。在这三个国家都跑完之后就遍历一遍，取min即可
dis[a][i][j]记录点i，j到国家a的距离，最后遍历一遍dis数组即可。
AC代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m;
char ch[1005][1005];
//bool vis[1005][1005];
int  dis[4][1005][1005];
int mov[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
#define pa pair<int, int>
#define x first
#define y second

bool judge(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m || ch[x][y] == '#' )
        return true;
    return false;
}

void bfs(int a)
{
    deque<pa> q;
    //memset(vis, 0,sizeof(vis));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(ch[i][j] - '0' == a)
            {
                q.push_back({i, j});
                dis[a][i][j] = 0;
                //vis[i][j] = 1;
            }
        }
    }

    while(!q.empty())
    {
        pa now = q.front();
        q.pop_front();
        for(int i = 0; i < 4; ++i)
        {
            int fx = now.x + mov[i][0];
            int fy = now.y + mov[i][1];
            if(judge(fx, fy))   continue;
            //vis[fx][fy] = 1;
            int k = (ch[fx][fy] == '.');
            if(dis[a][fx][fy] > dis[a][now.x][now.y] + k)
            {
                dis[a][fx][fy] = dis[a][now.x][now.y] + k;
                if(k)   q.push_back({fx, fy});
                else    q.push_front({fx, fy});
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%s", ch[i] + 1);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            for(int k = 1; k <= 3; ++k)
                dis[k][i][j] = 1e8;
        }
    }
    bfs(1), bfs(2), bfs(3);
    int ans = 1e8;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(ch[i][j] == '#') continue;
            int k = 0;
            if(ch[i][j] == '.') k = 2;
            //一个点只需要铺一次，所以是.的话需要-2
            ans = min(ans, dis[1][i][j] + dis[2][i][j] + dis[3][i][j] - k);
        }
    }
    if(ans == 1e8)  printf("-1\n");
    else    printf("%d\n", ans);
    return 0;
}