首页 > ACM题库 > HDU-杭电 > HDU 3850-Puzzling Maze[解题报告]HOJ
2015
04-13

HDU 3850-Puzzling Maze[解题报告]HOJ

Puzzling Maze

问题描述 :

Little A has a lovely toy dog , and she likes it so much . But bad B envy her happiness . So he robbed her little dog and put it in his partner C’s house. C’s house is like a big maze,so it’s so hard for A to find her toy . So she employed some robots to help her . These robots’ travel has some principles .

They’re listed as follows:

1.One robot can move horizontal and vertical, and it cannot stay at the start grid and not move.

2.Every robot’s path must be a circuit .

3.Every two robots’ travel path can not cross at any grid,and any grid in the maze must be stepped once and only once.

4.We don’t consider the direction those robots move.

5. You can use any numbers of robots, and there are infinitely many robots.

Only after traveling to every grid can A find her toy dog,she wonders how many ways to do this by using robots ?

输入:

The maze is like an "L" ,as show below. There are multiple test case. Each case contains 2 integers,n and m. We guarantee that m>=n,m<=10^9,1<=n<=7.
By Recognizing These Guys, We Find Social Networks Useful

输出:

The maze is like an "L" ,as show below. There are multiple test case. Each case contains 2 integers,n and m. We guarantee that m>=n,m<=10^9,1<=n<=7.
By Recognizing These Guys, We Find Social Networks Useful

样例输入:

2 2
2 3
2 4

样例输出:

Case 1: 1
Case 2: 1
Case 3: 4
Hint
Answers to the sample input are shown below .
By Recognizing These Guys, We Find Social Networks Useful
By Recognizing These Guys, We Find Social Networks Useful
By Recognizing These Guys, We Find Social Networks Useful
By Recognizing These Guys, We Find Social Networks Useful
By Recognizing These Guys, We Find Social Networks Useful
By Recognizing These Guys, We Find Social Networks Useful

#include <stdio.h>
#include <string.h>
#define maxn 150
#define mod 1000000007
struct matrix{
	int v[70][70];
	void clear(){
		memset(v,0,sizeof(v));
	}
} a,b;
int st_num[maxn],stn;
int n,m;
int ans;
int f[10][10][maxn];
int q[2][maxn],qn[2];
void dfs(int p,int mask,int st){
	if (p==n){
		if ((mask&(1<<n))==0){
			a.v[st_num[st]][st_num[mask]]++;
		}
		return;
	}
	int c1=((mask>>p)&1),c2=((mask>>p+1)&1);
	if (c1 && c2){
		dfs(p+1,mask^(1<<p)^(1<<p+1),st);
	}else
	if (c1 || c2){
		dfs(p+1,mask,st);
		dfs(p+1,mask^(1<<p)^(1<<p+1),st);
	}else{
		dfs(p+1,mask^(1<<p)^(1<<p+1),st);
	}
}
matrix mat_mul(matrix a,matrix b){
	matrix c;
	for (int i=0;i<stn;i++)
		for (int j=0;j<stn;j++){
			c.v[i][j]=0;
			for (int k=0;k<stn;k++)
				c.v[i][j]=(c.v[i][j]+(long long)a.v[i][k]*b.v[k][j])%mod;
		}
	return c;
}
matrix Mul(int p){
	matrix ret,ta=a;
	ret.clear();
	for (int i=0;i<stn;i++) ret.v[i][i]=1;
	while (p){
		if ((p&1)>0) ret=mat_mul(ret,ta);
		ta=mat_mul(ta,ta);
		p>>=1;
	}
	return ret;
}
inline int getBit(int mask,int p){
	return (mask>>p)&1;
}
inline void Add(int &x,int v){
	x=(x+v)%mod;
}
int cal(int st1,int st2,int c1,int c2){
	int ret=0;
	int now=0,next;
	qn[0]=1;
	q[0][0]=st1;
	memset(f,0,sizeof(f));
	
	for (int i=0;i<n;i++){
		next=now^1;
		qn[next]=0;
		for (int p=0;p<qn[now];p++){
			int st=q[now][p];
			if (i==0 || getBit(st,n)==getBit(st2,i-1)){
				if (i==0){
					f[0][0][st<<1]=1;
					q[next][qn[next]++]=st<<1;
				}else{
					int nst=st;
					if (getBit(st2,i-1)) nst-=(1<<n);
					Add(f[i][0][nst<<1],f[i-1][n][st]);
					q[next][qn[next]++]=nst<<1;
				}
			}
		}
		now=next;
		// if (i==1){
			// for (int c=0;c<qn[now];c++) printf("%d ",f[i][0][q[now][c]]);puts("");
		// }
		
		for (int j=0;j<n;j++){
			next=now^1;
			qn[next]=0;
			for (int p=0;p<qn[now];p++){
				int st=q[now][p],nst;
				int c1=getBit(st,j),c2=getBit(st,j+1);
				// if (i==1 && j==1) printf("!%d %d %d\n",st,c1,c2);
				if (c1 && c2){
					nst=st^(1<<j)^(1<<j+1);
					if (f[i][j+1][nst]==0){
						q[next][qn[next]++]=nst;
					}
					Add(f[i][j+1][nst],f[i][j][st]);
				}else
				if (c1 || c2){
					nst=st;
					// if (i==1 && j==1) printf("%d\n",nst);
					if (f[i][j+1][nst]==0){
					
						// if (i==1 && j==1) printf("%d\n",nst);
						q[next][qn[next]++]=nst;
					}
					Add(f[i][j+1][nst],f[i][j][st]);
					
					nst=st^(1<<j)^(1<<j+1);
					// if (i==1 && j==1) printf("%d\n",nst);
					if (f[i][j+1][nst]==0){
						// if (i==1 && j==1) printf("%d\n",nst);
						q[next][qn[next]++]=nst;
					}
					Add(f[i][j+1][nst],f[i][j][st]);
				}else{
					nst=st^(1<<j)^(1<<j+1);
					if (f[i][j+1][nst]==0){
						q[next][qn[next]++]=nst;
					}
					Add(f[i][j+1][nst],f[i][j][st]);
				}
			}
			now=next;
		}
	}
	for (int i=0;i<qn[now];i++){
		int st=q[now][i];
		if (getBit(st,n)==getBit(st2,n-1)){
			int nst=st;
			if (getBit(st,n)) nst-=(1<<n);
			if (nst==0) Add(ret,f[n-1][n][st]);
		}
	}
	long long tmp=ret;
	tmp*=c1;
	tmp%=mod;
	tmp*=c2;
	tmp%=mod;
	ret=tmp;
	return ret;
}
int main(){
	int cp=0;
	while (scanf("%d%d",&n,&m)!=EOF){
		printf("Case %d: ",++cp);
		if (n%2){
			puts("0");
			continue;
		}
		stn=0;
		memset(st_num,-1,sizeof(st_num));
		for (int i=0;i<(1<<n);i++){
			int k=0;
			for (int j=0;j<n;j++)
				if ((i&(1<<j))>0) k++;
			if (k%2==0){
				st_num[i]=stn++;
			}
		}
		a.clear();
		for (int i=0;i<(1<<n);i++)
			if (st_num[i]>-1) dfs(0,i<<1,i);
		b=Mul(m-n);
		
		ans=0;
		for (int i=0;i<(1<<n);i++)
			for (int j=0;j<(1<<n);j++){
				int si=st_num[i],sj=st_num[j];
				if (b.v[0][si] && b.v[0][sj]) ans=(ans+cal(i,j,b.v[0][si],b.v[0][sj]))%mod;
			}
		printf("%d\n",ans);
	}
	return 0;
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。