HDOJ - 2238 机器人的舞蹈II

HDOJ - 2238 机器人的舞蹈II

清明去乡下扫了一圈墓~~回来把这题A了...首先说一下这题和HDOJ-2232的区别...这道题描述上和2232的区别就是本题的机器人是一样的...2232里的机器人是不同的...那么造成的区别在于转移的时候差别...如有

4   0                  2   2                                         (1,2)  (3,4)    (1,3)  (2,4)

0   0       ---->    0   0     如果是不同机器人..那么   0        0    与   0        0  是不同的两种走位...而当所有机器人相同得情况..这两种走位是同一个走位...但走位的结果..不论机器人相同与否..状态是一样的..

所以这两题从状态上来说是一样的...差别仅在于状态转移时的方案数不同...

构造矩阵就用搜索...枚举从每个状态在一单位时间的变化下能有几种方式转化为另一个状态...也就是DFS了..

HDOJ-2232是每一层枚举移动一个机器人.枚举了4层后得到枚举出来的矩阵..判断是那个矩阵(通过翻转,对称阿..)..然后两者方案数++

而本题在构造矩阵时稍微麻烦一些....并不是枚举每个机器人怎么走..而是每局每个格子上的机器人怎么来分配...如

4 0

0  0

可以分解成3个向右,1个向下 或 2个向右,2个向下..等等之类的...这样直接讨论这个格子的机器人如何分配...就避免了由于机器人相同,而用2232的方法枚举机器人时有先后顺序关系而造成的错误了...

AC代码:

#include #include #include #include

构造矩阵的程序:

#include#define N 8using namespace std;int s[N][4]={{1,1,1,1}};int a[N][N],p,temp[4],i,T[4],W[4],z;int judge(){ int x,i,t,p; for (i=0;i<4;i++) temp[i]=T[i]; for (i=0;i<5;i++) { t=temp[0]; temp[0]=temp[1]; temp[1]=temp[3]; temp[3]=temp[2]; temp[2]=t; for (p=0;p<=z;p++) { for (x=0;x<4;x++) if (temp[x]!=s[p][x]) goto A; return p; A: ; } } temp[0]=T[2]; temp[2]=T[0]; temp[1]=T[3]; temp[3]=T[1]; for (i=0;i<5;i++) { t=temp[0]; temp[0]=temp[1]; temp[1]=temp[3]; temp[3]=temp[2]; temp[2]=t; for (p=0;p<=z;p++) { for (x=0;x<4;x++) if (temp[x]!=s[p][x]) goto B; return p; B: ; } } z++; for (i=0;i<4;i++) s[z][i]=T[i]; return z;}void DFS(int k){ int x,y; if (k==4) { a[p][judge()]++; return; } for (x=0;x<=s[p][k];x++) for (y=0;y<=s[p][k]-x;y++) { if (k==0) { T[k+1]+=x; T[k]-=x; T[k+2]+=y; T[k]-=y; DFS(k+1); T[k+1]-=x; T[k]+=x; T[k+2]-=y; T[k]+=y; }else if (k==1) { T[k-1]+=x; T[k]-=x; T[k+2]+=y; T[k]-=y; DFS(k+1); T[k-1]-=x; T[k]+=x; T[k+2]-=y; T[k]+=y; }else if (k==2) { T[k+1]+=x; T[k]-=x; T[k-2]+=y; T[k]-=y; DFS(k+1); T[k+1]-=x; T[k]+=x; T[k-2]-=y; T[k]+=y; }else if (k==3) { T[k-1]+=x; T[k]-=x; T[k-2]+=y; T[k]-=y; DFS(k+1); T[k-1]-=x; T[k]+=x; T[k-2]-=y; T[k]+=y; } } return;}int main(){ freopen("Matrix.txt","w",stdout); memset(a,0,sizeof(a)); int i,j; z=0; for (p=0;p<=z;p++) { for (i=0;i<4;i++) T[i]=s[p][i]; DFS(0); } z++; for (i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。