题解 P2243 【电路维修】

明显的一个搜索。
将每个方格的四个点都提出来,
若该方格的电线为‘\’,则给左上的点和右下的点连一条边权为$0$的边,给右上的点和左下的点连一条边权为$1$的边;
若为‘/’,则给左上的点和右下的点连一条边权为$1$的边,给右上的点和左下的点连一条边权为$0$的边。
即如下图所示(图画的不好见谅)。
思路很明确,这不就是个最短路吗,不过很抱歉这题把普通的$SPFA$给卡掉了
所以这题应用堆优化$DJ$或是$SPFA+SLF+LLL$优化。
但是,这题实际上是可以用双端广搜解决的,而且理论上应该比上述两方法还要快!
因为这题边权只有$0$和$1$两种情况,所以可以用双端广搜。
实现方法就是在广搜过程中找到了一条边,
若边权为$1$,则和正常广搜一样从队尾入队;若边权为$0$,则从队首入队。
即在广搜过程中保持队列单调性,使其每次都能优先遍历边权为$0$的边。
不过我可能敲了个奇葩的算法,貌似是双端$SPFA$??
感觉跑的速度比原汁原味的双端广搜要慢,但又比最短路算法快??
不管怎样还是先上代码吧。

#include<cstdio>
#include<cstring>
using namespace std;
const int N=3e5+10;
const int M=3e6+10;
int fi[N],di[M],da[M],ne[M],dis[N],nxt[M],nmb[M],n,m,l;
bool v[N];
//fi,di,da,ne为存边数值,dis记录距离,v记录点有无经过
//nxt,nmb则为数组模拟链表
//nxt记录下一个空间(即后驱),nmb则为这个空间对应的数据
//因为要实现从队首入队的话自然使用链表是不错的
//而我嫌STL常数过大,所以是用数组来模拟链表
inline int re()//快读
{
    int x=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+(c-'0');
    return x;
}
inline int re_l()//读取方格数据并判断是'/'还是'\'的函数
{
    char c=getchar();
    for(;c!='\\'&&c!='/';c=getchar());
    return c=='/'?1:0;
}
inline void add(int x,int y,int z)//加边
{
    di[++l]=y;
    da[l]=z;
    ne[l]=fi[x];
    fi[x]=l;
    di[++l]=x;
    da[l]=z;
    ne[l]=fi[y];
    fi[y]=l;
}
inline int ch(int x,int y)//给每个点一个标签
{
    return (x-1)*(m+1)+y;
}
int main()
{
    int i,j,x,y,t,head,tail,s,ed;
    bool p=1;
    t=re();
    while(t--)//多组数据
    {
        n=re();
        m=re();
        head=l=0;//初始化&清空数组
        s=tail=1;
        p=1;
        ed=ch(n+1,m+1);
        memset(fi,0,sizeof(fi));
        memset(v,0,sizeof(v));
        memset(dis,50,sizeof(dis));
        memset(nxt,0,sizeof(nxt));
        memset(nmb,0,sizeof(nmb));
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)//输入方格数据
            {
                if(re_l())//加边方法即为前面所述
                {
                    add(ch(i,j),ch(i+1,j+1),1);
                    add(ch(i+1,j),ch(i,j+1),0);
                }
                else
                {
                    add(ch(i,j),ch(i+1,j+1),0);
                    add(ch(i+1,j),ch(i,j+1),1);
                }
            }
        dis[1]=0;//初始化
        v[1]=1;
        nxt[0]=1;
        nmb[1]=1;
        while(p)//p用来记录有无到达终点,有则直接退出
        {
            head=nxt[head];//每次通过后驱到下一个空间
            if(!head)//若没有后驱了就表明搜索完毕
                break;
            x=nmb[head];//取出该空间对应的数
            for(i=fi[x];i&&p;i=ne[i])//枚举边
            {
                y=di[i];
                if(!v[y]||dis[y]>dis[x]+da[i])//如果没有遍历过或是之前遍历的并不是最短的
                {
                    s++;//给链表申请一个新空间
                    if(da[i])//判断边权
                    {//若为1则从队尾入队
                        nxt[tail]=s;//在链表末端空间打上后驱
                        tail=s;//更新末端
                    }
                    else//若为0则从队首入队
                    {
                        nxt[s]=nxt[head];
                        //将目前遍历的空间的后驱过继给新增空间
                        //即将原本队列置于新增空间后面
                        nxt[head]=s;
                        //将目前遍历的空间的后驱改为新增空间
                        //这样下一次循环就能先遍历新增空间了
                        //于是就实现了将新增空间置于队首的功能
                        if(!nxt[s])
                            tail=s;
                        //一个小细节
                        //若目前队列为空,即队首就是队尾的情况
                        //也要更新末端
                    }
                    nmb[s]=y;//给新增空间附上数值
                    v[y]=1;//记录该点
                    dis[y]=dis[x]+da[i];//修改距离
                    if(y==ed)//若到达终点,直接退出搜索
                        p=0;
                }
            }
        }
        if(p)//若没有到达终点说明无解
            printf("NO SOLUTION\n");
        else
            printf("%d\n",dis[ed]);
    }
    return 0;
}

该奇葩算法跑了$460ms$,而我的朴素$SPFA$在开$O^2$的情况下跑了$2784ms$,且最后一个点为$932ms$,勉强卡了过去,可见该奇葩算法的效率还是挺高的。
下面上下巨佬$lyd$的标准双端广搜,跑了$204ms$。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int cap = 500010;
int dist[510][510]; char map[510][510]; bool proc[510][510];
pair<int, int> queue[cap * 2]; int r, c, li, ri;
inline bool valid (int x, int y) { return x >= 0 && x <= r && y >= 0 && y <= c; }
inline void que_add (int x, int y, int v)
{
    if (dist[x][y] < 0 || v < dist[x][y])
    {
        dist[x][y] = v;
        if (li == ri || v > dist[queue[li].first][queue[li].second]) queue[ri++] = make_pair(x, y);
        else queue[--li] = make_pair(x, y);
    }
}
int main ()
{
    int kase; for (scanf("%d", &kase); kase; --kase)
    {
        scanf("%d %d", &r, &c);
        if ((r + c) % 2)
        {
            for (int i = 0; i < r; i++) scanf("%s", map[i]);
            printf("NO SOLUTION\n");
        }
        else
        {
            for (int i = 0; i < r; i++) scanf("%s", map[i]);
            li = ri = cap; queue[ri++] = make_pair(0, 0);
            memset(dist, -1, sizeof dist), dist[0][0] = 0;
            memset(proc, false, sizeof proc);
            while (li != ri)
            {
                int cx = queue[li].first, cy = queue[li].second; ++li;
                if (valid(cx - 1, cy - 1))
                {
                    if (map[cx - 1][cy - 1] == '\\') que_add(cx - 1, cy - 1, dist[cx][cy]);
                    else que_add(cx - 1, cy - 1, dist[cx][cy] + 1);
                }
                if (valid(cx - 1, cy + 1))
                {
                    if (map[cx - 1][cy] == '/') que_add(cx - 1, cy + 1, dist[cx][cy]);
                    else que_add(cx - 1, cy + 1, dist[cx][cy] + 1);
                }
                if (valid(cx + 1, cy - 1))
                {
                    if (map[cx][cy - 1] == '/') que_add(cx + 1, cy - 1, dist[cx][cy]);
                    else que_add(cx + 1, cy - 1, dist[cx][cy] + 1);
                }
                if (valid(cx + 1, cy + 1))
                {
                    if (map[cx][cy] == '\\') que_add(cx + 1, cy + 1, dist[cx][cy]);
                    else que_add(cx + 1, cy + 1, dist[cx][cy] + 1);
                }
            }
            printf("%d\n", dist[r][c]);
        }
    }
    return 0;
}
//因为是从lyd巨佬所著书的光盘里复制的,所以侵删

发表于 2018-04-17 20:16:49 in 题解