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 – 页面初始化时让组件得不到焦点