Beyond the Void
BYVoid
USACO 5.4.4 Betsy's Tour 漫遊小鎮 betsy
本文正體字版由OpenCC轉換

這道題要使用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;
    }
    

    上次修改時間 2017-02-03

    相關日誌