Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
萌妹纸1A留念~/******** poj1739 2016.1.11 452K 79MS C++ 4937B ********/ #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int MAXD=15; const int HASH=30007;//一个比实际容量稍大的素数 const int STATE=1000010;//哈希表的最大元素个数 using namespace std; int N,M; int maze[MAXD][MAXD]; int code[MAXD]; int ch[MAXD];//最小表示法使用 int ex,ey;//最后一个非障碍格子的坐标 struct HASHMAP { int head[HASH],next[STATE],size; long long state[STATE]; long long f[STATE]; void init() { size=0; memset(head,-1,sizeof(head));//用单独链表法处理碰撞 } void push(long long st,long long ans)//key->value { int i; int h=st%HASH; for(i=head[h];i!=-1;i=next[i])//这里要注意是next if(state[i]==st)//找到了此键值 { f[i]+=ans;//键值已存在,在这种状态下只是把次数加进去就好啦 return; } state[size]=st; f[size]=ans; next[size]=head[h]; head[h]=size++; } }hm[2]; void decode(int *code,int m,long long st)//把某行上的轮廓信息解成一个code数组 { for(int i=m;i>=0;i--) { code[i]=st&7;//要是只有2中状态就&1呗 st>>=3; } } long long encode(int *code,int m)//最小表示法 m<=12显然只有6个不同的连通分量 { int cnt=1; memset(ch,-1,sizeof(ch)); ch[0]=0; long long st=0; for(int i=0;i<=m;i++) { if(ch[code[i]]==-1)ch[code[i]]=cnt++;//新发现一个 code[i]=ch[code[i]]; st<<=3;//0~7 8进制表示 st|=code[i];//<==>st+=code[i] } return st;//返回最终次轮廓上的连通分量信息 } void shift(int *code,int m)//当到最后一列的时候,相当于需要把code中所有元素向右移一位 { for(int i=m;i>0;i--)code[i]=code[i-1]; code[0]=0; } void dpblank(int i,int j,int cur)//cur是当前状态,操作之后就是cur^1啦 总共就三大种情况 逐个讨论一下就好 { int k,left,up; for(k=0;k<hm[cur].size;k++) { decode(code,M,hm[cur].state[k]); left=code[j-1]; up=code[j]; if(left&&up) { if(left==up)//只能出现在最后一个非障碍格子 { if(i==ex&&j==ey) { code[j-1]=code[j]=0;//最终合并成一个回路 if(j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); } } else//不在同一个连通分量则合并成同一个 { code[j-1]=code[j]=0; for(int t=0;t<=M;t++)//所谓的O(n)复杂度 if(code[t]==up) code[t]=left; if(j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); } } else if((left&&(!up))||((!left)&&up))//写的真墨迹 直接left||up就得了呗 右下没有插头则连出来一个 {//对于当前格子(i,j)code[j-1]是它左侧的格子插头信息,code[j]是它右边的格子插头信息 //处理后:code[j-1]是(i,j)下方格子插头信息,code[j]是~右边格子插头信息 int t; if(left)t=left; else t=up; if(maze[i][j+1])//右边没有障碍 { code[j-1]=0; code[j]=t; hm[cur^1].push(encode(code,M),hm[cur].f[k]); } if(maze[i+1][j])//下边没有障碍 { code[j-1]=t; code[j]=0; if(j==M)shift(code,M); hm[cur^1].push(encode(code,M),hm[cur].f[k]); } } else//无插头,则构造新的连通块 { if(maze[i][j+1]&&maze[i+1][j]) { code[j-1]=code[j]=13;//只要是一个没出现过的就好,因为代入函数不涉及它到底是几 hm[cur^1].push(encode(code,M),hm[cur].f[k]); } } } } void dpblock(int i,int j,int cur)//一个障碍是不可能有向下和向右的插头的,那就设其为0 { int k; for(k=0;k<hm[cur].size;k++) { decode(code,M,hm[cur].state[k]);//解码 code[j-1]=code[j]=0; if(j==M)shift(code,M);//换行 hm[cur^1].push(encode(code,M),hm[cur].f[k]);//毕竟是向后走了一格 //把当前的数据cur=0压到另一个位置cur=1==>把当前的数据cur=1压到另一个位置cur=0 } } char str[MAXD]; void init() { memset(maze,0,sizeof(maze)); for(int i=1;i<=N;i++) { scanf("%s",&str); for(int j=0;j<M;j++) { if(str[j]=='.') { maze[i][j+1]=1; } } } ex=N+2,ey=M; for(int j=1;j<=M;j++) maze[N+1][j]=0; maze[N+1][1]=maze[N+1][M]=1; for(int j=1;j<=M;j++) maze[N+2][j]=1; } void solve() { int i,j,cur=0; long long ans=0; hm[cur].init();//cur=0 hm[cur].push(0,1);//加入没插头的状态cur=0 for(i=1;i<=N+2;i++) for(j=1;j<=M;j++) { hm[cur^1].init();//每到一个位置,把另一组清零 清空cur=1==>清空cur=0 if(maze[i][j])dpblank(i,j,cur);//当前这个进行设置。计算cur=0==>计算cur=1 else dpblock(i,j,cur); cur^=1;//cur变成了另一个数cur=1==>变成了cur=0 } for(i=0;i<hm[cur].size;i++)//现在的cur要是放在循环里就是待计算的位置 ans+=hm[cur].f[i];//各种状态的和就是总的可能的方案数 printf("%I64d\n",ans); } int main() { //freopen("cin.txt","r",stdin); while(scanf("%d%d",&N,&M)!=EOF) { if(N==0&&M==0) break; init(); if(M==1)//没有空的格子 { printf("0\n"); continue; } solve(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator