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