题解：UVA838 Worm World

思路

暴搜即可：是裸题，先初始边界为

{-1}

表示没法走，然后暴力搜索每一个可能的路径并且如果该路径够长就更新答案（绝对裸题，但是优化自己想，比如控制两个相同数字的点的尽可能长的路径，但是两秒够暴搜了）。时间复杂度为

{\mathcal{O}(G \times N^{2} \times 4^{K})}

（最坏情况下）。其中

{G}

是组数，

{N}

是图的大小，

{4^{K}}

是所有可能走过的路径总数。

代码

CPP

#include<iostream>
#include<cstring>
using namespace std;
int Map[14][14],Answ=-1000;
int Dx[5]={0,-1,1,0,0};//4个方向  .
int Dy[5]={0,0,0,-1,1};//4个方向  ,
int Buc[1000001]={0};//标记是否经过该数字
void Dfs(int X,int Y,int Ans);
int main()
{
    int G;
    scanf("%d",&G);
    while(G--)
    {
        int S;
        Answ=-1e9;
        scanf("%d",&S);
        for(int Ind=0;Ind<=S+1;Ind++)
        {
            Map[0][Ind]=Map[Ind][0]=Map[S+1][Ind]=Map[Ind][S+1]=-1;//初始化边界。
        }
        for(int IndI=1;IndI<=S;IndI++)
        {
            for(int IndJ=1;IndJ<=S;IndJ++)
            {
                scanf("%d",&Map[IndI][IndJ]);
            }
        }
        memset(Buc,0,sizeof(Buc));
        for(int IndI=1;IndI<=S;IndI++)
        {
            for(int IndJ=1;IndJ<=S;IndJ++)
            {
                Buc[Map[IndI][IndJ]]=1;//暴力搜索的前标记。
                Dfs(IndI,IndJ,1);
                Buc[Map[IndI][IndJ]]=0;//暴力搜索的后擦除。
            }
        }
        printf("%d\n",Answ);
    }
    return 0;
}
void Dfs(int X,int Y,int Ans)
{
    if(Answ<Ans)Answ=Ans;//更新答案，因为 Ans 为在当前路径中的最后一步，显然比上一步更优。
    for(int Ind=1;Ind<=4;Ind++)
    {
        int Nx=X+Dx[Ind];
        int Ny=Y+Dy[Ind];
        if(Map[Nx][Ny]==-1)continue;//判断是否边界。
        if(Buc[Map[Nx][Ny]]!=0)continue;//判断是否访问过这个数字。
        Buc[Map[Nx][Ny]]=1;//搜索下一步。
        Dfs(Nx,Ny,Ans+1);
        Buc[Map[Nx][Ny]]=0;//回溯上一步。
    }
}

数据

一个比较大的数据如下：

PLAIN

[In]
1
8
 6  8 18 15 24 20  2 20
 6  2 15  2 17 15  3  7
 0 11 18 16 20 15  1 11
 6  2  6 13  4 17 20 16
 5 12  7  2  3  5 18 23
 7 13  3  2  2 11  4 23
16 23 10  2  4 12  5 20
17 12 10  1 13 12  6 20

（建议看图前图片。）
而输出是

PLAIN

[Out]
20

结

广告位：博客。

题解：UVA838 Worm World

文章操作

思路

代码

数据

结

相关推荐

评论

题解：UVA838 Worm World