首页 > 代码库 > uva-211-The Domino Effect
uva-211-The Domino Effect
http://uva.onlinejudge.org/external/2/211.html
http://uva.onlinejudge.org/external/2/211.pdf
题意:每一种骨牌(Bone) 对应了两个球(Pip)。球的数值从0-6,骨牌从1-28。
然后给你一个包含球数值的矩阵(7*8),问你什么样的骨牌会形成这样的球的矩阵。
注意,题目有一个信息没有讲明白,那就是每种骨牌只能取一个,并且要取到所有的28种骨牌。7*8/28 = 2.
思路:对于每种骨牌,先从矩阵中寻找可以形成该骨牌的球对。有些骨牌可以有多种形成方式,
而有些骨牌则可能只有一种形成方式,因此这里要先考虑形成方式少的骨牌,排序!
之后,就暴力枚举每种骨牌的形成方式,有冲突的就pass。
#include<ctime> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<iostream> #include<map> #include<string> #include<queue> using namespace std; #define FOR(i,a,b) for(int i=a;i<b;i++) #define FORE(i,a,b) for(int i=a;i<=b;i++) #define FORD(i,a,b) for(int i=a;i>b;i--) #define FORDE(i,a,b) for(int i=a;i>=b;i--) #define SCF(a) scanf("%d",&a) #define SCF2(a,b) scanf("%d%d",&a,&b) #define SCF3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define SCFS(a) scanf("%s",a) #define SCFC(a) scanf("%c",&a) #define PRT(a) printf("%d",a); #define PRTC(a) printf("%c",a); #define PRTLN(a) printf("%d\n",a); #define PRTLNU(a) printf("%lld\n",a); #define PRTS(a) printf("%s\n",a); #define min2(a,b) ((a)<(b))?(a):(b) #define max2(a,b) ((a)>(b))?(a):(b) #define MST(a,b) memset(a,b,sizeof(a)); #define swap(a,b) (a=(a)^(b),b=(a)^(b),a=(a)^(b)) #define pb push_back typedef struct{ vector<int> lis; int i,c; }DAT; DAT dat[28]; int ID[7][7]; int mat[7][8]; int ret[7][8]; int sol; bool cmp(const DAT a,const DAT b){ return a.c>b.c; } void initID(){ int k = 0; FORE(i,0,6) FORE(j,i,6) ID[j][i] = ID[i][j] = k++; } void init(){ sol=0; FOR(i,0,28){ dat[i].lis.clear(); dat[i].i=i; } //down i-0 FOR(i,0,6) FOR(j,0,8) dat[ID[mat[i][j]][mat[i+1][j]]].lis.pb(i*8+j); //right j-1 FOR(i,0,7) FOR(j,0,7) dat[ID[mat[i][j]][mat[i][j+1]]].lis.pb(i*8+j+56); FOR(i,0,28) dat[i].c = dat[i].lis.size(); sort(dat,dat+28,cmp); MST(ret,0); } bool isok(int s){ if(s<56) return !ret[s/8][s%8] && !ret[1 + s/8][s%8]; else{ s = s%56; return !ret[s/8][s%8] && !ret[s/8][1 + s%8]; } } void assign(int s,int x){ if(s<56) ret[s/8][s%8] = ret[1 + s/8][s%8] = x; else{ s = s%56; ret[s/8][s%8] = ret[s/8][1 + s%8] = x; } } void print(int (*ret)[8]){ FOR(i,0,7){ FOR(j,0,8) printf("%4d",ret[i][j]); printf("\n"); } printf("\n"); } void dfs(int k){ if(k<0){ print(ret); sol++; return; } FOR(i,0,dat[k].c) if(isok(dat[k].lis[i])){ assign(dat[k].lis[i],dat[k].i+1); dfs(k-1); assign(dat[k].lis[i],0); } } int main(){ //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); int cse = 1; initID(); while(~SCF(mat[0][0])){ FOR(s,1,56) SCF(mat[s/8][s%8]); init(); if(cse>1) printf("\n\n\n",cse); printf("Layout #%d:\n\n",cse); print(mat); printf("Maps resulting from layout #%d are:\n\n",cse); dfs(27); printf("There are %d solution(s) for layout #%d.\n",sol,cse); cse ++; } //fclose(stdout); //fclose(stdin); //system("pause"); return 0; } /* 5 4 3 6 5 3 4 6 0 6 0 1 2 3 1 1 3 2 6 5 0 4 2 0 5 3 6 2 3 2 0 6 4 0 4 1 0 0 4 1 5 2 2 4 4 1 6 5 5 5 3 6 1 2 3 1 4 2 5 2 6 3 5 4 5 0 4 3 1 4 1 1 1 2 3 0 2 2 2 2 1 4 0 1 3 5 6 5 4 0 6 0 3 6 6 5 4 0 1 6 4 0 3 0 6 5 3 6 2 1 5 3 */
uva-211-The Domino Effect
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。