首页 > ACM题库 > HDU-杭电 > HDU 4026-Unlock the Cell Phone-动态规划-[解题报告]HOJ
2015
04-15

HDU 4026-Unlock the Cell Phone-动态规划-[解题报告]HOJ

Unlock the Cell Phone

问题描述 :

Modern high-tech cell phones use unlock patterns to unlock the system. The pattern is usually a 3*3 dot array. By moving your finger over there dots, you can generate your personal unlock pattern. More specifically, press your finger over any starting dot, then slide all the way to the next dot, touch it, and so on. Jumping is not allowed. For example, starting from dot 1, you can slide to touch dot 2, dot 4 and dot 5, but sliding directly to dot 3, dot 7 or dot 9 are not allowed. Note that sliding from 1 to 6 and 8 is also allowed because they are not considered as jumping over any dot. However, you can jump a dot if it has been touched before. For example, staring with 1-5-9-6, you can slide directly to dot 4.
Equation of XOR

Here is a very particular cell phone. It has a dot array of size n*m. Some of the dots are ordinary ones: you can touch, and slide over them when touched before; some are forbidden ones: you cannot touch or slide over them; some are inactive ones: you cannot touch them, but can slide over them. Each dot can only be touched once. You are required to calculate how many different unlock patterns passing through all the ordinary dots.

输入:

The input contains several test cases. Each test case begins with a line containing two integers n and m (1 <= n, m <= 5), indicating the row and column number of the lock keypad. The following n lines each contains m integers kij indicating the properties of each key, kij=0 stands for an ordinary key, kih=1 stands for a forbidden key; and kij=2 stands for an inactive key. The number of ordinary keys is greater than zero and no more than 16.

输出:

The input contains several test cases. Each test case begins with a line containing two integers n and m (1 <= n, m <= 5), indicating the row and column number of the lock keypad. The following n lines each contains m integers kij indicating the properties of each key, kij=0 stands for an ordinary key, kih=1 stands for a forbidden key; and kij=2 stands for an inactive key. The number of ordinary keys is greater than zero and no more than 16.

样例输入:

2 2
0 0
0 0
3 3
0 0 0
0 2 1
0 0 0

样例输出:

24
2140

这题比赛的时候没写出来,当时理解错题意了,这题意有点不清楚,是一个触屏机的解锁系统,问你有多少种方案。

原来可以任意角度进行滑行,不过不能跳过没按的,简单的来说就是经过所有要按的点,然后要满足这个点是否有一条路线到达这个点,就是这里感觉处理异常困难,分析一下,走过的点可以跳过,那就是按了后还是可以经过的,那么不能经过的点有哪些呢?首先标记为1的点不能经过,为0且没有经过的点,其他点都可以经过。这题的关键不是这里,这样依然会超时,记忆化优话也是tle,关键是gcd,太慢了,可以先预处理了一下,才5*5,一下子就不知道快了多少。

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
4579377 2011-09-10 22:40:38 Accepted 4026 2156MS 8516K 1628 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
	int x,y;
}nd[16];
long long dp[1<<16][16];//状态和当前到达的点
int n,m,gp[6][6],pos,gd[6][6],mp[6][6];
int gcd(int x,int y)
{
	 if (y == 0)
        return x;
    return gcd(y, x % y);
}
bool ok(int x,int y,int sta)
{
	int x1=nd[x].x,x2=nd[y].x,y1=nd[x].y,y2=nd[y].y;
	int dx=x2-x1;
	int dy=y2-y1;
	int c=gd[abs(dx)][abs(dy)];
	dx=dx/c;dy=dy/c;
	for(int i=0;i<=5;i++)
	{
		x1+=dx;y1+=dy;
		if(gp[x1][y1]==1)
			return false;
		else if(x1==x2&&y1==y2)
			return true;
		else if(gp[x1][y1]==0&&(sta&(1<<(mp[x1][y1])))==0)
			return false;
	}
	return false;
}

long long DP(int st,int k)
{
	if(dp[st][k]!=-1)return dp[st][k];
	if(st==(1<<k)) dp[st][k]=1;
	else
	{
		dp[st][k]=0;
		for(int j=0;j<pos;j++)
		{
			if(((1<<j)&st)==0||j==k)continue;
			if(ok(j,k,st)==0)continue;
			dp[st][k]+=DP(st-(1<<k),j);	
		}
	}
		return dp[st][k];
}
void work()
{
	long long ans=0;
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<pos;i++)
	      DP((1<<pos)-1,i);
	for(int i=0;i<pos;i++)
	{
			ans+=dp[(1<<pos)-1][i];
	}
	cout<<ans<<'\n';
}
void init()
{
	for(int i=0;i<6;i++)
		for(int j=0;j<6;j++)
			gd[i][j]=gcd(i,j);
}
int main()
{
	init();
	while(scanf("%d%d",&n,&m)!=EOF)
	{	
		pos=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				scanf("%d",&gp[i][j]);
				if(gp[i][j]==0)
				{
					nd[pos].x=i;
					nd[pos++].y=j;
					mp[i][j]=pos-1;
				}
			}
			work();
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xymscau/article/details/6766700


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!