优化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
小阮 阅读(555)
评论(0) 编辑 收藏 引用 所属分类:
USACO