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 8
using 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;}elseif (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;                      }elseif (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;                           }elseif (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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！