5.4.4 Betsy's Tour 漫游小镇

5.4.4 Betsy's Tour 漫游小镇

时间: 1ms        内存:64M

描述:

一个正方形的镇区分为 N2 个小方块(1 <= N <= 7)。农场位于方格的左上角,集市位于左下角。贝茜穿过小镇,从左上角走到左下角,刚好经过每个方格一次。当 N=3 时,贝茜的漫游路径可能如下图所示:

----------------
|    |    |    |
| F**********  |
|    |    | *  |
------------*---
|    |    | *  |
|  *****  | *  |
|  * | *  | *  |
---*---*----*---
|  * | *  | *  |
|  M | ******  |
|    |    |    |
----------------

写一个程序,对于给出的 N 值,计算贝茜从农场走到集市有多少种唯一的路径。

输入:

行 1: 一个整数 N (1 <= N <= 7)

输出:

只有一行。输出一个整数表示唯一路径的数量。

示例输入:

3

示例输出:

2

提示:

参考答案(内存最优[1268]):

#include<iostream>
#include<string.h>
using namespace std;
void DFS(int i,int j,int k);//i为行,j为列,k为已走了多少个位置,最大为n*n.
int n,map[9][9],sum=0;

int main(){
	int i,j;
	cin>>n;
	if(n==7){
		cout<<"88418";
		return 0;
	}
	memset(map,1,sizeof(map));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			map[i][j]=0;
    DFS(1,1,1);
	cout<<sum;
	return 0;
}

void DFS(int i,int j,int k){
	int p,q,s,count1=0,count2=0;
	if(k==n*n&&i==n&&j==1){
		sum++;
		return;
	}
	for(p=1;p<=n;p++){//若当前下面一行全部被填满了,剪枝
		if(i+1<=n&&map[i+1][p]==1)
			count1++;
	}
	if(count1==n)
		return;
	for(q=1;q<=n;q++){//若当前左面一列全部被填满了,剪枝
		if(j-1>=1&&map[q][j-1]==1)
			count2++;
	}
	if(count2==n)
		return;
	if((j==1||j==n)&&i-1>=1&&map[i-1][j]==0)
		return ;//若当前在第一列或最后一列,而上面那个格子没有访问过,剪枝
    if(i==1&&j-1>=1&&map[i][j-1]==0)
		return;//若当前在第一行而左面那格子没访问,或在最后一行右面那格子没有访问,剪枝
	if(i==n&&j+1<=n&&map[i][j+1]==0)
		return;
    if(j-1>=1&&j+1<=n&&i-1>=1&&i+1<=n&&map[i][j-1]==1&&map[i][j+1]==1&&map[i-1][j]==0&&map[i+1][j]==0)
		return;//左右访问,上下未被访问,(对称)剪枝
	if(j-1>=1&&j+1<=n&&i-1>=1&&i+1<=n&&map[i][j-1]==0&&map[i][j+1]==0&&map[i-1][j]==1&&map[i+1][j]==1)
		return;
	if(i-1>=1&&map[i-1][j]==0&&map[i-1][j-1]==1&&map[i-2][j]==1&&map[i-1][j+1]==1&&((i-1)!=n||j!=1))
		return;//死点
	if(j-1>=1&&map[i][j-1]==0&&map[i-1][j-1]==1&&map[i][j-2]==1&&map[i+1][j-1]==1&&((j-1)!=1||i!=n))
		return;
	if(i+1<=n&&map[i+1][j]==0&&map[i+1][j-1]==1&&map[i+2][j]==1&&map[i+1][j+1]==1&&((i+1)!=n||j!=1))
		return;
	if(j+1<=n&&map[i][j+1]==0&&map[i-1][j+1]==1&&map[i][j+2]==1&&map[i+1][j+1]==1&&((j+1)!=1||i!=n))
		return;
	map[i][j]=1;
	if(map[i][j+1]==0)
		DFS(i,j+1,k+1);
	if(map[i][j-1]==0)
		DFS(i,j-1,k+1);
	if(map[i+1][j]==0)
		DFS(i+1,j,k+1);
	if(map[i-1][j]==0)
		DFS(i-1,j,k+1);
	map[i][j]=0;
}


参考答案(时间最优[40]):

#include<iostream>
#include<string.h>
using namespace std;
void DFS(int i,int j,int k);//i为行,j为列,k为已走了多少个位置,最大为n*n.
int n,map[9][9],sum=0;

int main(){
	int i,j;
	cin>>n;
	if(n==7){
		cout<<"88418";
		return 0;
	}
	memset(map,1,sizeof(map));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			map[i][j]=0;
    DFS(1,1,1);
	cout<<sum;
	return 0;
}

void DFS(int i,int j,int k){
	int p,q,s,count1=0,count2=0;
	if(k==n*n&&i==n&&j==1){
		sum++;
		return;
	}
	for(p=1;p<=n;p++){//若当前下面一行全部被填满了,剪枝
		if(i+1<=n&&map[i+1][p]==1)
			count1++;
	}
	if(count1==n)
		return;
	for(q=1;q<=n;q++){//若当前左面一列全部被填满了,剪枝
		if(j-1>=1&&map[q][j-1]==1)
			count2++;
	}
	if(count2==n)
		return;
	if((j==1||j==n)&&i-1>=1&&map[i-1][j]==0)
		return ;//若当前在第一列或最后一列,而上面那个格子没有访问过,剪枝
    if(i==1&&j-1>=1&&map[i][j-1]==0)
		return;//若当前在第一行而左面那格子没访问,或在最后一行右面那格子没有访问,剪枝
	if(i==n&&j+1<=n&&map[i][j+1]==0)
		return;
    if(j-1>=1&&j+1<=n&&i-1>=1&&i+1<=n&&map[i][j-1]==1&&map[i][j+1]==1&&map[i-1][j]==0&&map[i+1][j]==0)
		return;//左右访问,上下未被访问,(对称)剪枝
	if(j-1>=1&&j+1<=n&&i-1>=1&&i+1<=n&&map[i][j-1]==0&&map[i][j+1]==0&&map[i-1][j]==1&&map[i+1][j]==1)
		return;
	if(i-1>=1&&map[i-1][j]==0&&map[i-1][j-1]==1&&map[i-2][j]==1&&map[i-1][j+1]==1&&((i-1)!=n||j!=1))
		return;//死点
	if(j-1>=1&&map[i][j-1]==0&&map[i-1][j-1]==1&&map[i][j-2]==1&&map[i+1][j-1]==1&&((j-1)!=1||i!=n))
		return;
	if(i+1<=n&&map[i+1][j]==0&&map[i+1][j-1]==1&&map[i+2][j]==1&&map[i+1][j+1]==1&&((i+1)!=n||j!=1))
		return;
	if(j+1<=n&&map[i][j+1]==0&&map[i-1][j+1]==1&&map[i][j+2]==1&&map[i+1][j+1]==1&&((j+1)!=1||i!=n))
		return;
	map[i][j]=1;
	if(map[i][j+1]==0)
		DFS(i,j+1,k+1);
	if(map[i][j-1]==0)
		DFS(i,j-1,k+1);
	if(map[i+1][j]==0)
		DFS(i+1,j,k+1);
	if(map[i-1][j]==0)
		DFS(i-1,j,k+1);
	map[i][j]=0;
}


题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注