419      阿裏雲  技術社區[雲棲]

[usaco] 5.4.4 Betsy's Tour

 好久沒作usaco了。過了個年，人都懶了。

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

這次的主要是減枝。

當到達一個格子後，下一個格子選擇哪裏呢？答案是，如果這個格子的旁邊如果有個格子，該格子周圍隻有一個未訪問格子時，就選擇這個格子。
當然終點除外了。

Executing...
   Test 1: TEST OK [0.000 secs, 3180 KB]
   Test 2: TEST OK [0.000 secs, 3180 KB]
   Test 3: TEST OK [0.000 secs, 3180 KB]
   Test 4: TEST OK [0.000 secs, 3180 KB]
   Test 5: TEST OK [0.000 secs, 3180 KB]
   Test 6: TEST OK [0.011 secs, 3180 KB]
   Test 7: TEST OK [0.346 secs, 3180 KB]

/*
ID:yunleis2
PROG:betsy
LANG:C++
*/

#include<iostream>
#include<fstream>
using namespace std;
#define MAXN 10
#define  DEBUG
int N;
bool visited[MAXN][MAXN];
int nabor[MAXN][MAXN];
int total=0;
void travel(int x,int y,int n);
#define minusOne(nx,ny,one) {if(!visited[nx][ny]){	if((--nabor[nx][ny])==1&&!((nx==N&&ny==1)))		++one; }}
#define forwordOne(nx,ny,nth)    if(!visited[nx][ny]&&nabor[nx][ny]==1){ travel(nx,ny,nth+1);}
#define forword(nx,ny,nth)    if(!visited[nx][ny]){ travel(nx,ny,nth+1);}
#define rollback(nx,ny)   if(!visited[nx][ny]) nabor[nx][ny]++;
void print();
int main(){

	ifstream  fin("betsy.in");
	fin>>N;
	for(int i=1+1;i<N;++i){
		for(int j=1+1;j<N;++j){
			nabor[i][j]=4;
		}
	}
	for(int i=0;i<N+2;++i)
		visited[0][i]=visited[N+1][i]=true;
	for(int i=0;i<N+2;++i)
		visited[i][0]=visited[i][N+1]=true;
	for(int i=1+1;i<N;++i)
		nabor[1][i]=nabor[N][i]=3;
	for(int i=1+1;i<N;++i)
		nabor[i][1]=nabor[i][N]=3;
	nabor[1][1]=nabor[N][N]=nabor[N][1]=nabor[1][N]=2;
#ifdef DEBUG

	print();
	
#endif
	travel(1,1,1);
	ofstream fout("betsy.out");
	fout<<total<<endl;
	//system("pause");
}
void print(){
	for(int i=0;i<N+2;++i){
		for(int j=0;j<N+2;++j){
			cout<<nabor[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	for(int i=0;i<N+2;++i){
		for(int j=0;j<N+2;++j){
			cout<<visited[i][j]<<" ";
		}
		cout<<endl;
	}
	
}
void travel(int x,int y,int nth){
	if(y==1&&x==(N)){
		if(nth!=N*N)
			return;
		++total;
		return;
	}
	
	visited[x][y]=true;
	int one=0;
	 minusOne(x-1,y,one);
	 minusOne(x,y-1,one);
	 minusOne(x+1,y,one);
	 minusOne(x,y+1,one);
//	cout<<x<<" ,"<<y<<endl;
//	print();
	if(one==1){		
		forwordOne(x-1,y,nth);
		forwordOne(x,y-1,nth);
		forwordOne(x+1,y,nth);
		forwordOne(x,y+1,nth);
	}
	else if(one==0)
	{
		forword(x-1,y,nth);
		forword(x,y-1,nth);
		forword(x+1,y,nth);
		forword(x,y+1,nth);
	}
	rollback(x-1,y);
	rollback(x,y-1);
	rollback(x+1,y);
	rollback(x,y+1);
	visited[x][y]=false;
	//roolback
}

最後更新：2017-04-02 22:16:26

  上一篇： Ubuntu 11.04 添加筆記本的觸摸板的管理工具

  下一篇： android – 頁麵初始化時讓組件得不到焦點