随笔-141  评论-9  文章-3  trackbacks-0

优化1:黑书P184, 一条完整的路径对于中间各点(除起点和目标点外),必需包含一进一出,所以中间点必需至少有两个未经过的相邻点(除非当前点在旁边)

优化2:预防形成孤零区域。

/*
ID: lorelei3
TASK: betsy
LANG: C++
*/


#include 
<fstream>

using namespace std;

const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
const int MAXN = 10;

ifstream fin(
"betsy.in");
ofstream fout(
"betsy.out");

bool map[MAXN][MAXN];

int n,ans,num;
void input(){
    fin
>>n;
    
for(int i=0; i<=n+1++i){
        map[
0][i]=true, map[i][0]=true, map[n+1][i]=true, map[i][n+1]=true;
    }

    num
=n*n;
}


inline 
int get(int x, int y){
    
int cnt=0;
    
for(int i=0; i<4++i)
        
if(!map[x+dx[i]][y+dy[i]])
            cnt
++;
    
return cnt;
}


void dfs(int x, int y, int t){
    
if(x==n&&y==1){
        
if(t==num)
            ans
++;
        
return;
    }


    
//优化2
    if(map[x][y-1]&&map[x][y+1]&&!map[x+1][y]&&!map[x-1][y] ||
        
!map[x][y-1]&&!map[x][y+1]&&map[x+1][y]&&map[x-1][y] )
        
return;

    
//优化1
    int i,xi,yi,count=0;
    
for(i=0; i<4++i){
        
int tx=x+dx[i];
        
int ty=y+dy[i];
        
if(map[tx][ty] || (tx==n&&ty==1))
            
continue;
        
int p = get(tx,ty);
        
if(p<=1){
            count
++;
            xi
=tx, yi=ty;
        }

    }


    
if(count>1)
        
return;
    
else{
        
if(count==1){
            map[xi][yi]
=true;
            dfs(xi,yi,t
+1);
            map[xi][yi]
=false;
        }
else{
            
for(i=0; i<4++i){
                
int tx=x+dx[i];
                
int ty=y+dy[i];
                
if(!map[tx][ty]){
                    map[tx][ty]
=true;
                    dfs(tx,ty,t
+1);
                    map[tx][ty]
=false;
                }

            }

        }

    }

}


void solve(){
    map[
1][1]=true;
    dfs(
1,1,1);
}




void output(){
    fout
<<ans<<endl;
}


int main(){

    input();

    solve();

    output();

    
return 0;
}


posted on 2011-02-16 15:28 小阮 阅读(595) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理