奶牛选美题解

发表于 | | 本文总阅读量 次

奶牛选美(双端队列解法及代码)

算法标签：双端队列bfs

题目大意：求为了将两个由’X’组成的连通块连通起来，最少需要将多少个’.’变为’X’。

1：思路分析： （后面有具体解释)

首先，我们可以任取一个值为’X’的点作为bfs的起点(，然后，在bfs的过程中，我们建立双端队列q，首先把距离数组初始化为充分大的常数INF,然后把起点的距离设为0，并把起点加入队列，当队列不空时，我们取出队头元素，如果队头元素对应的值为’X’，且其到起点的距离不为0，那么直接返回其距离即可，这就是最终答案。否则，通过st数组判断这个点到起点的最短距离是否已经算过了，如果没算过，那么和Dijkstra算法类似，我们将其对应的st数组设置为1，代表它的最短距离已经确定，然后用这个点来更新它周围四个点的距离。

如果周围的点是’.’那么权重w为1，否则为0 如果可以更新，那么将新扩展到的点的距离更新。并且，如果w为0，那么将新扩展到的点加入队头，否则，加入队尾

模型及具体解释

这道题目的模型属于双端队列模型。之所以将权重为0的点加入队头，而将权重为1的点加入队尾的原因是这样操作之后，队列中元素距离起点的距离仍然是单调递增的，所以，这样求出来的距离才是最短距离(与堆优化的Dijkstra类似)。

此外，之所以可以随便选择一个’X’作为起点，也是由于我们将’X’的权重设为了0，所以不会影响最终的答案。其实，这道题就等价于求从起点到终点的最小步数，这不过，题目中的步数实际上是指将’X’变为’.’的操作。而当我们扩展到另一个’X’ 且其距离不为0时，这个X肯定是和起点的‘X’不属于同一连通块(否则其最短距离就应该是0)，而通过bfs，求出的是最短距离，自然，我们此时返回的就是所求的答案了。

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<deque>
#include<cstring>
using namespace std;
const int N=55;
typedef pair<int,int>PII; 
int n,m,st[N][N],d[N][N];
char g[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int bfs(int sx,int sy)
{
    deque<PII>q;
    memset(d,0x3f,sizeof d);
    q.push_back({sx,sy});
    d[sx][sy]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop_front();
        int a=t.first,b=t.second;
        if(g[a][b]=='X'&&d[a][b]) return d[a][b];
        if(st[a][b]) continue;
        st[a][b]=1;
        for(int i=0;i<4;i++)
        {
            int nx=a+dx[i],ny=b+dy[i];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            int w=g[nx][ny]=='.';
            if(d[nx][ny]>d[a][b]+w)
            {
                d[nx][ny]=d[a][b]+w;
                if(!w) q.push_front({nx,ny});
                else q.push_back({nx,ny});
            }
        }
    }
    return 66666;
}
int main()
{ 
    cin>>n>>m;
    int t1,t2;
    for(int i=0;i<n;i++)  cin>>g[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            {
                if(g[i][j]=='X')
                {
                    t1=i,t2=j;
                    break;
                }
            }
            cout<<bfs(t1,t2);
}

##时间复杂度分析：通过双端队列的优化可以达到线性的时间复杂度。

有不对的地方欢迎指正，有不懂的地方欢迎大家提问！
题解的博客地址:https://acshine.github.io/