USACO 5.4.4 Betsy's Tour 漫游小镇 betsy

这道题要使用DFS加上优化才可以过。
朴素的搜索只能解决到N=5,6会超时。于是要加上一些优化。

优化1
不走死胡同!所谓死胡同,就是走进去以后就再也无法走出来的点。

一种简单的想法是:"任意时刻,必须保证和当前所在位置不相邻的未经点至少有两个相邻的未经点"。基于这种想法,可以采取这样的优化:

  • 当前点周围的点D,如果只有一个与D相邻的未经点,则点D为必经点
  • 显然,如果当前点周围有两个或两个以上的符合上述条件的必经点,则无论走哪个必经点都会造成一个死胡同,需要剪枝。
  • 如果当前点周围只有一个必经点,则一定要走到这个点。
  • 如果该点周围没有必经点,则需要枚举周围每一个点。
  • 该优化的力度很大,可以在0.2秒内解决N=6,但N=7仍然需要2秒左右的时间。

    优化2
    不要形成孤立的区域!如果行走过程中把路一分为二,那么肯定有一部分再也走不到了,需要剪枝。

    形成孤立的区域的情况很多,如果使用Floodfill找连通快,代价会很大,反而会更慢。我只考虑了一种最容易出现特殊情况,即:

  • 当前点左右都是已经点(包括边缘),而上下都是未经点
  • 当前点上下都是已经点(包括边缘),而左右都是未经点
  • 这样就会形成孤立的区域,只要将出现这种情况的状态都剪掉即可。

    加上优化2,N=7也能在0.3s解决了。

    Compiling...
    Compile: OK

    Executing...
    Test 1: TEST OK [0.000 secs, 2844 KB]
    Test 2: TEST OK [0.000 secs, 2840 KB]
    Test 3: TEST OK [0.000 secs, 2844 KB]
    Test 4: TEST OK [0.000 secs, 2840 KB]
    Test 5: TEST OK [0.000 secs, 2840 KB]
    Test 6: TEST OK [0.011 secs, 2840 KB]
    Test 7: TEST OK [0.302 secs, 2840 KB]

    All tests OK.

    Your program ('betsy') produced all correct answers! This is your submission #5 for this problem. Congratulations!

    /*
    ID: cmykrgb1
    PROG: betsy
    LANG: C++
    */
    
    #include <iostream>
    #include <fstream>
    #define MAX 9
    
    using namespace std;
    
    ifstream fi("betsy.in");
    ofstream fo("betsy.out");
    
    int N,N_2,cnt;
    bool map[MAX][MAX];
    int pi[4]={0,0,1,-1},pj[4]={1,-1,0,0};
    
    void init()
    {
        int i,j,k;
        fi >> N;
        N_2=N*N;
        for (i=0;i<=N+1;i++)
        {
            map[0][i]=map[N+1][i]=map[i][0]=map[i][N+1]=true;
        }
        map[1][1]=1;
    }
    
    void print()
    {
        fo << cnt << endl;
        fi.close();
        fo.close();
    }
    
    inline int getfree(int i,int j)
    {
        int v=0;
        for (int k=0;k<4;k++)
        {
            if (!map[ i+pi[k] ][ j+pj[k] ])
                v++;
        }
        return v;
    }
    
    void go(int i,int j,int step)
    {
        if (i==N && j==1)
        {
            if (step==N_2)
                cnt++;
            return;
        }
    
        if    (
                (map[i][j-1] && map[i][j+1] && !map[i-1][j] && !map[i+1][j])
                ||
                (!map[i][j-1] && !map[i][j+1] && map[i-1][j] && map[i+1][j])
            )
            return;
    
        int k,di,dj,f,cntf=0,ki,kj;
        for (k=0;k<4;k++)
        {
            di=i+pi[k],dj=j+pj[k];
            if (map[di][dj] || (di==N && dj==1)) continue;
            f=getfree(di,dj);
            if (f<2)
            {
                cntf++;
                ki=di;
                kj=dj;
            }
        }
    
        if (cntf>1)
            return;
        else
        {
            if (cntf==1)
            {
                map[ki][kj]=true;
                go(ki,kj,step+1);
                map[ki][kj]=false;
            }
            else
            {
                for (k=0;k<4;k++)
                {
                    di=i+pi[k],dj=j+pj[k];
                    if (!map[di][dj])
                    {
                        map[di][dj]=true;
                        go(di,dj,step+1);
                        map[di][dj]=false;
                    }
                }
            }
        }
    }
    
    int main()
    {
        init();
        go(1,1,1);
        print();
        return 0;
    }
    

    相关日志