一本通第四章-广搜的优化技巧 题解

   题解    0 条评论   

肝总结肝的我肝疼。

10026.电路维修

把题意转化一下,可以把每个端点看成节点,有导线相连的对角线就连一条边权为0的边,不相连的对角线就连一条边权为1的边。

然后用最短路什么的做就行了。看题解里面说最短路比较慢,再加上本来就该练习广搜,我就写了双向广搜。

struct Edge{
    int next,to,w,from;
} edge[1000005];
int n,m,t,cnt,head[251005],dis[251005];
bool vis[251005];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].from=u;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline int to_line(int x,int y)
{
    return (x-1)*(m+1)+y;
}

inline bool bfs()
{
    deque <int> q;
    memset(vis,0,sizeof(vis));
    q.push_front(1);
    vis[1]=1;
    while (!q.empty())
    {
        int x=edge[q.front()].from,y=edge[q.front()].to,w=edge[q.front()].w; q.pop_front();
        if (vis[y]) continue;
        vis[y]=1;
        dis[y]=dis[x]+w;
        if (y==(n+1)*(m+1)) return 1;
        for (int i=head[y];i;i=edge[i].next)
        {
            if (vis[edge[i].to]) continue;
            if (edge[i].w) q.push_back(i);
            else q.push_front(i);
        }
    }
    return 0;
}

inline void init()
{
    cnt=0;
    memset(dis,0,sizeof(dis));
    memset(head,0,sizeof(head));
}

int main()
{
    t=read();
    while (t--)
    {
        init();
        n=read(); m=read();
        for (int i=1;i<=n;i++)
        {
            char s[505];
            scanf("%s",s+1);
            for (int j=1;j<=m;j++)
            {
                int x1=to_line(i+1,j),y1=to_line(i,j+1),x2=to_line(i,j),y2=to_line(i+1,j+1);
                if (s[j]=='/')
                {
                    add(x2,y2,1); add(y2,x2,1);
                    add(x1,y1,0); add(y1,x1,0);
                }
                else
                {
                    add(x2,y2,0); add(y2,x2,0);
                    add(x1,y1,1); add(y1,x1,1);
                }
            }
        }
        if (!bfs()) printf("NO SOLUTION\n");
        else printf("%d\n",dis[(n+1)*(m+1)]);
    }
    return 0;
}

10027.魔板

这个广搜本身挺显然的,但我很傻逼。在每种操作后的结果如果被搜索过我都写了continue,然后就会跳过剩下的操作,然后我就调了半天。发现了也懒得重构了,直接用goto

struct node{
    int s[10],id;
} stat;
string ans[370005];
int goal[10],goal_id,vis[370005];
int fac[]={1,1,2,6,24,120,720,5040,40320};

inline int get_hash(int *s) //康托展开去重
{
    int ans=0;
    for (int i=1;i<=9;i++)
    {
        int sm=0;
        for (int j=i+1;j<=9;j++)
            if (s[j]<s[i]) sm++;
        ans+=fac[8-i+1]*sm;
    }
    return ans;
}

inline int bfs()
{
    queue <node> q;
    q.push(stat);
    vis[stat.id]=1;
    while (!q.empty())
    {
        node x=q.front(); q.pop();
        node bef=x;

        int s[5];
        memcpy(s+1,x.s+1,4*sizeof(int));
        memcpy(x.s+1,x.s+5,4*sizeof(int));
        memcpy(x.s+5,s+1,4*sizeof(int));
        x.id=get_hash(x.s);
        if (vis[x.id]) goto Case_B;
        vis[x.id]=vis[bef.id]+1;
        ans[x.id]=ans[bef.id]+"A";
        if (x.id==goal_id) return vis[x.id];
        q.push(x);

        Case_B:;
        x=bef;
        int a=x.s[4],b=x.s[8];
        for (int i=4;i>=2;i--) x.s[i]=x.s[i-1];
        for (int i=8;i>=6;i--) x.s[i]=x.s[i-1];
        x.s[1]=a; x.s[5]=b;
        x.id=get_hash(x.s);
        if (vis[x.id]) goto Case_C;
        vis[x.id]=vis[bef.id]+1;
        ans[x.id]=ans[bef.id]+"B";
        if (x.id==goal_id) return vis[x.id];
        q.push(x);

        Case_C:;
        x=bef;
        a=x.s[2];
        x.s[2]=x.s[6];
        x.s[6]=x.s[7];
        x.s[7]=x.s[3];
        x.s[3]=a;
        x.id=get_hash(x.s);
        if (vis[x.id]) continue;
        vis[x.id]=vis[bef.id]+1;
        ans[x.id]=ans[bef.id]+"C";
        if (x.id==goal_id) return vis[x.id];
        q.push(x);
    }
    return vis[goal_id];
}

int main()
{
    for (int i=1;i<=8;i++) 
    {
        int now=(i<=4) ? i : 13-i;
        goal[now]=read();
        stat.s[i]=now;
    }
    goal_id=get_hash(goal);
    stat.id=get_hash(stat.s);
    printf("%d\n",bfs()-1);
    cout<<ans[goal_id];
    return 0;
}

10028.Knight Moves

不是很懂为什么一道比一道简单。

int t,n,sx,sy,ex,ey,vis[305][305];
int fx[8]={1,2,2,1,-1,-2,-2,-1},fy[8]={2,1,-1,-2,-2,-1,1,2};

inline int bfs()
{
    queue <pr> q;
    q.push(mp(sx,sy));
    memset(vis,0,sizeof(vis));
    vis[sx][sy]=1;
    while (!q.empty())
    {
        int x=q.front().first,y=q.front().second; q.pop();
        for (int i=0;i<8;i++)
        {
            int tx=x+fx[i],ty=y+fy[i];
            if (tx<1 || tx>n || ty<1 || ty>n || vis[tx][ty]) continue;
            vis[tx][ty]=vis[x][y]+1;
            if (tx==ex && ty==ey) return vis[ex][ey]-1;
            q.push(mp(tx,ty));
        }
    }
    return vis[ex][ey]-1;
}

int main()
{
    t=read();
    while (t--)
    {
        n=read(); sx=read()+1; sy=read()+1; ex=read()+1; ey=read()+1;
        if (sx==ex && sy==ey) printf("0\n");
        else printf("%d\n",bfs());
    }
    return 0;
}

10029.棋盘游戏

三倍经验:洛谷P4289loj10031(没错你没有看错就是同一章就有重题!)

这个广搜也挺裸的,搜索4个方向进行交换,转化为二进制判重即可。需要注意的是对struct里的变量用swap()好像会出锅,我因为这个调了很久。

struct node{
    int s[5][5],id;
} stat,goal;
int vis[100005];
int fx[4]={0,-1,0,1},fy[4]={1,0,-1,0};

inline int get_hash(int s[5][5])
{
    int now=32768,ans=0;
    for (int i=1;i<=4;i++)
    {
        for (int j=1;j<=4;j++)
        {
            ans+=s[i][j]*now;
            now>>=1;
        }
    }
    return ans;
}

inline int bfs()
{
    queue <node> q;
    q.push(stat);
    vis[stat.id]=1;
    while (!q.empty())
    {
        node x=q.front(); q.pop();
        node bef=x;
        for (int i=1;i<=4;i++)
        {
            for (int j=1;j<=4;j++)
            {
                if (!x.s[i][j]) continue;
                for (int k=0;k<4;k++)
                {
                    int tx=i+fx[k],ty=j+fy[k];
                    if (tx<1 || tx>4 || ty<1 || ty>4) continue;
                    if (x.s[tx][ty]) continue;
                    x.s[i][j]=0; x.s[tx][ty]=1;
                    x.id=get_hash(x.s);
                    if (vis[x.id]) 
                    {
                        x=bef;
                        continue;
                    }
                    vis[x.id]=vis[bef.id]+1;
                    if (x.id==goal.id) return vis[x.id]-1;
                    q.push(x);
                    x=bef;
                }
            }
        }
    }
    return vis[goal.id]-1;
}

int main()
{
    for (int i=1;i<=4;i++)
    {
        char ch[5];
        scanf("%s",ch+1);
        for (int j=1;j<=4;j++) stat.s[i][j]=ch[j]-'0';
    }
    stat.id=get_hash(stat.s);
    for (int i=1;i<=4;i++)
    {
        char ch[5];
        scanf("%s",ch+1);
        for (int j=1;j<=4;j++) goal.s[i][j]=ch[j]-'0';
    }
    goal.id=get_hash(goal.s);
    printf("%d\n",bfs());
    return 0;
}

10030.Keyboarding

这道应该是最难的了吧。

https://llf0703.com/p/uva-1714.html

10031.移动玩具

同10029

10032.山峰和山谷

用bfs求联通块,然后判断它们是不是山峰和山谷即可。

pr ans;
int n,s[1005][1005];
bool vis[1005][1005];
int fx[8]={-1,-1,-1,0,0,1,1,1},fy[8]={1,0,-1,1,-1,1,0,-1};

inline pr bfs(int st_x,int st_y)
{
    queue <pr> q;
    q.push(mp(st_x,st_y));
    vis[st_x][st_y]=1;
    pr ans=mp(1,1);
    while (!q.empty())
    {
        int x=q.front().first,y=q.front().second; q.pop();
        for (int i=0;i<8;i++)
        {
            int tx=x+fx[i],ty=y+fy[i];
            if (tx<1 || tx>n || ty<1 || ty>n) continue;
            //if (vis[tx][ty]) continue;
            if (s[x][y]==s[tx][ty] && !vis[tx][ty])
            {
                vis[tx][ty]=1;
                q.push(mp(tx,ty));
            }
            else if (s[x][y]<s[tx][ty]) ans.first=0;
            else if (s[x][y]>s[tx][ty]) ans.second=0;
        }
    }
    return ans;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            s[i][j]=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (vis[i][j]) continue;
            pr now=bfs(i,j);
            ans.first+=now.first;
            ans.second+=now.second;
        }
    }
    printf("%d %d",ans.first,ans.second);
    return 0;
}

以上。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
This work is licensed under a CC BY-SA 4.0 International License .

本文链接:https://llf0703.com/p/ybt-4.html


添加新评论