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;
    }
    

    相關日誌