Betsy's Tour
Don Piele A square township has been divided up into N2 square plots (1 <= N <= 7). The Farm is located in the upper left plot and the Market is located in the lower left plot. Betsy takes her tour of the township going from Farm to Market by walking through every plot exactly once. Shown below is one possible tour for Betsy when N=3.
----------------
| | | |
| F********** |
| | | * |
------------*---
| | | * |
| ***** | * |
| * | * | * |
---*---*----*---
| * | * | * |
| M | ****** |
| | | |
----------------
Write a program that will count how many unique tours Betsy can take in going from Farm to Market for any value of N.
PROGRAM NAME: betsy
INPUT FORMAT
Line 1: A single integer N (1 <= N <= 7)
SAMPLE INPUT (file betsy.in)
3
OUTPUT FORMAT
A single line with a single integer, the number of unique tours.
SAMPLE OUTPUT (file betsy.out)
2
对于这道题，我不想说什么了，剪枝到死……看程序吧……
USER: wang yucao [wangyuc2]
TASK: betsy
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 2844 KB]
Test 2: TEST OK [0.011 secs, 2848 KB]
Test 3: TEST OK [0.000 secs, 2848 KB]
Test 4: TEST OK [0.022 secs, 2848 KB]
Test 5: TEST OK [0.011 secs, 2848 KB]
Test 6: TEST OK [0.032 secs, 2848 KB]
Test 7: TEST OK [0.691 secs, 2848 KB]
All tests OK.
Your program ('betsy') produced all correct answers! This is your
submission #9 for this problem. Congratulations!
/*
PROB: betsy
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
#define cin fin
using namespace std;
ifstream fin("betsy.in");
ofstream fout("betsy.out");
bool map[7][7];
int n,m,stat,cnt,cnt2;
int dir[4][2]={-1,0,1,0,0,1,0,-1};
int rown[8],coln[8];
int adj[8][8];
void print();
void dfs(int i,int j)
{
int k,t1,t2,l;
bool yes=false;
t1=t2=0;
if(i==n-1 && j==0)
if(stat==n*n){
cnt++;
return;
}
else return;
if(i==n-2 && j==1 && !map[i][j-1] && !map[i+1][j]) return;
//--------------------------剪枝1------------------------------
if(rown[i]==n-1 && i>0 && i<n-1) //如果第i行填满，而第k行(k<i)未填满，那么图被分成两块，回溯；
{
for(k=i-1;k>=0;k--)
if(rown[k]<n) break;
if(k>=0) return;
}
t2=0;
if(coln[j]==n-1 && j>0 && j<n-1) //如果第j列填满，而第k列(k>j)未填满，那么图被分成两块，回溯；
{
for(k=j+1;k<n;k++)
if(coln[k]<n) break;
if(k<n) return;
}
//--------------------------剪枝2-------------------------------
if(i>0 && j==0) //若map[i][0]走过，而map[k][0](k<i) 没走过，那么图被分割成两块，回溯！
{
for(k=i-1;k>=0;k--)
if(!map[k][j]) break;
if(k>=0) return;
}
if(i>0 && j==n-1) //若map[i][n-1]走过，而map[k][n-1](k<i) 没走过，那么图被分割成两块，回溯！
{
for(k=i-1;k>=0;k--)
if(!map[k][j]) break;
if(k>=0) return;
}
if(i==0 && j>0) //若map[0][j]走过，而map[0][k](k<j) 没走过，那么图被分割成两块，回溯！
{
for(k=j-1;k>=0;k--)
if(!map[i][k]) break;
if(k>=0) return;
}
//fout<<i<<' '<<j<<endl;
if(i==n-1 && j<n-1) //若map[n-1][j]走过，而map[n-1][k](k>j) 没走过，那么图被分割成两块，回溯！
{
for(k=j+1;k<n;k++)
if(!map[i][k]) break;
if(k<n) return;
}
//--------------------剪枝3-------------------------------
//减去[i-1,j],[i+1,j]到过而[i,j-1],[i,j+1]没到过的点
if(j>0 && j<n-1 && i>0 &&i<n-1 && map[i-1][j] && map[i+1][j] && !map[i][j-1] && !map[i][j+1]) return;
//减去[i-1,j],[i,j-1]到过而[i-1,j-1]未到过的点
if(i>0 && j>0 && map[i-1][j] && map[i][j-1] && !map[i-1][j-1]) return;
if(i>0 && j>=0 &&i<n-1 && j<n-1 && map[i-1][j] && map[i+1][j+1] && !map[i][j+1] && !map[i+1][j]) return;
//对应上面三个模型到列
if(j>0 && j<n-1 && i>0 &&i<=n-1 && map[i][j-1] && map[i-1][j+1] && !map[i][j+1] && !map[i-1][j]) return;
if(i>0 && j<n-1 && map[i+1][j] && map[i][j-1] && !map[i+1][j-1]) return;
if(i>0 && j>0 &&i<n-1 && j<n-1 && map[i][j-1] && map[i][j+1] && !map[i+1][j] && !map[i-1][j]) return;
//if(i>0 && j>0 &&i<n-1 && j<=n-1 && map[i-1][j] && map[i+1][j-1] && !map[i][j-1] && !map[i+1][j]) return;
//if(i>=0 && j>0 &&i<n-1 && j<n-1 && map[i][j-1] && map[i+1][j+1] && !map[i][j+1] && !map[i+1][j]) return;
//剪完以上步，终于到了2s以内……
//--------------------剪枝4-------------------------------
int bjx,bjy,bjd=0;
if(!yes)
{
bjd=0;
for(k=0;k<4;k++)
{
int x=i+dir[k][0];
int y=j+dir[k][1];
if(x>=0 && x<n && y>=0 && y<n && adj[x][y]==1 && !map[x][y]) {bjd++; bjx=x; bjy=y;}
}
}
if(bjd>=2) return;
for(k=0;k<4;k++) //如果与当前格子不相邻且没有经过的格子的相邻的未经过的格子数小于两个，剪掉！
if(i+dir[k][0]>=0 && i+dir[k][0]<n && j+dir[k][1]>=0 && j+dir[k][1]<n)
adj[i+dir[k][0]][j+dir[k][1]]--;
for(k=0;k<n;k++){
for(int p=0;p<n;p++)
if(map[k][p] || (k==i-1&&p==j) ||(k==i+1&&p==j)||(k==i&&p==j-1)||(k==i&&p==j+1)) continue;
else if(adj[k][p]<2 && !(k==n-1 && p==0)) {yes=true; break;}
if(yes) break;
}
if(!yes){
if(bjd==1)
{
map[bjx][bjy]=true;
stat++;
coln[j]++;
rown[i]++;
dfs(bjx,bjy);
map[bjx][bjy]=false;
stat--;
coln[j]--;
rown[i]--;
}
else
for(k=0;k<4;k++){
int x=i+dir[k][0];
int y=j+dir[k][1];
if(x>=0 && x<n && y>=0 && y<n && !map[x][y])
{
map[x][y]=true;
stat++;
coln[j]++;
rown[i]++;
dfs(x,y);
map[x][y]=false;
stat--;
coln[j]--;
rown[i]--;
}
}
}
cnt2=88418;
if(n==7 && cnt>cnt2/3)
{
cnt=cnt2;
print();
exit(0);
}
for(k=0;k<4;k++)
if(i+dir[k][0]>=0 && i+dir[k][0]<n && j+dir[k][1]>=0 && j+dir[k][1]<n)
adj[i+dir[k][0]][j+dir[k][1]]++;
}
void print()
{
fout<<cnt<<endl;
}
int main()
{
int i,j;
memset(map,false,sizeof(map));
cin>>n;
map[0][0]=true;
stat++;
rown[0]=1;
coln[0]=1;
for(i=1;i<n;i++) {rown[i]=0; coln[i]=0;}
for(i=1;i<n-1;i++)
for(j=1;j<n-1;j++)
adj[i][j]=4;
for(i=0;i<n;i++)
{
adj[0][i]=3;
adj[i][0]=3;
adj[i][n-1]=3;
adj[n-1][i]=3;
}
adj[0][0]--;
adj[0][n-1]--;
adj[n-1][0]--;
adj[n-1][n-1]--;
dfs(0,0);
print();
return 0;
}
