Three States

吐槽下题目:不愧是cf,真的就是阅读理解,抛开复杂的题意,就是一个广搜,不过需要存三种情况.......
题意:现在有三个地盘,然后要修一条可以连通三个城市的道路,并且要最短,可以穿过其他人的地盘来连通
题解:记忆广搜,以每个点来广搜会超时,但是以每个地盘的数字来进行广搜就可以了
先把一个地盘的所有点压入队列,然后来广搜全局,再用数组记录当前到其他剩余点所需要的时间戳,
然后重复两次
最后遍历全图对于每个点来进行三个时间戳求和,取最小,即答案
时间复杂度:

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

struct node
{
    int x,y;
}r,f;
queue<node>Q;
int n,m,T[4][1005][1005],dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char R[1005][1005];
void BFS(int a)
{
    int i,j,X,Y;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            T[a][i][j]=1e8;
            if(R[i][j]-'0'==a)T[a][i][j]=0,r.x=i,r.y=j,Q.push(r);
        }
    while(!Q.empty())
    {
        f=Q.front(),Q.pop();
        for(i=0;i<4;i++)
        {
            X=f.x+dx[i],Y=f.y+dy[i],j=T[a][f.x][f.y];
            if(X<0||X>=n||Y<0||Y>=m||R[X][Y]=='#')continue;
            if(R[X][Y]=='.')j++;
            if(j<T[a][X][Y])T[a][X][Y]=j,r.x=X,r.y=Y,Q.push(r);
        }
    }
}
int main()
{
    int i,j,t,ans=1e8;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)scanf("%s",R[i]);
    BFS(1),BFS(2),BFS(3);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            if(R[i][j]=='#')continue;
            t=T[1][i][j]+T[2][i][j]+T[3][i][j];
            if(R[i][j]=='.')t-=2;
            ans=min(ans,t);
        }
    if(ans==1e8)ans=-1;
    printf("%d\n",ans);
}