欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 211 The Domino Effect

程序员文章站 2024-03-18 23:55:28
...

https://vjudge.net/problem/UVA-211

题目

给你28张“双六”多米诺骨牌,编号如下:

Bone #      Pips        Bone #      Pips        Bone #      Pips        Bone #      Pips
   1        0 | 0          8        1 | 1         15        2 | 3         22        3 | 6
   2        0 | 1          9        1 | 2         16        2 | 4         23        4 | 4
   3        0 | 2         10        1 | 3         17        2 | 5         24        4 | 5
   4        0 | 3         11        1 | 4         18        2 | 6         25        4 | 6
   5        0 | 4         12        1 | 5         19        3 | 3         26        5 | 5
   6        0 | 5         13        1 | 6         20        3 | 4         27        5 | 6
   7        0 | 6         14        2 | 2         21        3 | 5         28        6 | 6

 在7*8的网格中每张牌各摆一张,如图所示,左边是各个格子的点数,右边是各个格子所属的骨牌编号。

  7 x 8 grid of pips            map of bone numbers
                                
6  6  2  6  5  2  4  1        28 28 14  7 17 17 11 11
1  3  2  0  1  0  3  4        10 10 14  7  2  2 21 23
1  3  2  4  6  6  5  4         8  4 16 25 25 13 21 23
1  0  4  3  2  1  1  2         8  4 16 15 15 13  9  9
5  1  3  6  0  4  5  5        12 12 22 22  5  5 26 26
5  5  4  0  2  6  0  3        27 24 24  3  3 18  1 19
6  0  5  3  4  2  0  3        27  6  6 20 20 18  1 19

 输入左图,你的任务是输出所有可能的右图

题解

整理数据= =将每张牌的每个数字与另外一边的数字对应起来,可以加快搜索速度

只有28层,不用担心爆栈

太激动了……又是花一大堆时间写的一道题!(4小时)

UVA 211 The Domino Effect

(早睡早起.jpg)

AC代码

#include<bits/stdc++.h>
using namespace std;
#define REP(r,x,y) for(register int r=(x); r<(y); r++)
#define REPE(r,x,y) for(register int r=(x); r<=(y); r++)
#define MAXN 7
#define MAXM 8
#ifdef sahdsg
#define DBG(...) printf(__VA_ARGS__)
#else
#define DBG(...)
#endif
int mp[MAXN][MAXM];
int ans[MAXN][MAXM];
bool vis[29];
int ansc=0;
int bones[][2] =
{
	{-1,-1},{0,0},{0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{1,1},{1,2},{1,3},{1,4},{1,5},{1,6},{2,2},{2,3},{2,4},{2,5},{2,6},{3,3},{3,4},{3,5},{3,6},{4,4},{4,5},{4,6},{5,5},{5,6},{6,6}
};
int sq[][7]=
{
	{1*2,2*2+1,3*2+1,4*2+1,5*2+1,6*2+1,7*2+1},
	{2*2,8*2,9*2+1,10*2+1,11*2+1,12*2+1,13*2+1},
	{3*2,9*2,14*2,15*2+1,16*2+1,17*2+1,18*2+1},
	{4*2,10*2,15*2,19*2,20*2+1,21*2+1,22*2+1},
	{5*2,11*2,16*2,20*2,23*2,24*2+1,25*2+1},
	{6*2,12*2,17*2,21*2,24*2,26*2,27*2+1},
	{7*2,13*2,18*2,22*2,25*2,27*2,28*2}
};
inline bool getblock() {
	ansc=0;
	memset(ans,-1,sizeof ans);
	REP(i,0,7) REP(j,0,8) {
		if(scanf("%d", &mp[i][j])==-1) return false;
	}
	return true;
}
//int back;
bool dfs(int d, int x, int y) {
//	DBG("#%d\t%d\t%d\n", d, x, y);
	st:
	if(y>=8) y=0, x++;
	if(d>=28) {
		ansc++;
		REP(i,0,MAXN) {
			REP(j,0,MAXM) {
				if(j) putchar(' ');
				printf("%d", ans[i][j]);
			}
			putchar('\n');
		}
			putchar('\n');
		return true;
	}
	if(ans[x][y]!=-1) {
		y++; goto st;
	}
	int k=mp[x][y];
	bool f=false;
	REP(i,0,8) {
		int t=sq[k][i];
		int p=t&1; t>>=1;
		if(vis[t]) continue;
//		assert(t>0);
		if(x+1<7)
		if(mp[x+1][y]==bones[t][p] && ans[x+1][y]==-1) {
			f=true;vis[t]=true;
			ans[x][y]=t, ans[x+1][y]=t;
			dfs(d+1, x,y+1);
			ans[x][y]=-1, ans[x+1][y]=-1;
			vis[t]=false;
		}
		if(y+1<8)
		if(mp[x][y+1]==bones[t][p] && ans[x][y+1]==-1) {
			f=true;vis[t]=true;
			ans[x][y]=t, ans[x][y+1]=t;
			dfs(d+1, x,y+2);
			ans[x][y]=-1, ans[x][y+1]=-1;
			vis[t]=false;
		}
	}
	return f;
}

int main() {
	#ifdef sahdsg
	freopen("in.txt", "r", stdin);
	#endif
	int kase=0;
	while(getblock()) {
		if(kase) puts("\n\n");
		kase++;
		printf("Layout #%d:\n\n", kase);
		REP(i,0,7) {
			REP(j,0,8) {
				if(j) putchar(' ');
				printf("%d", mp[i][j]);
			}
			putchar('\n');
		}
		putchar('\n');
		printf("Maps resulting from layout #%d are:\n\n", kase);
		dfs(0,0,0);
		printf("There are %d solution(s) for layout #%d.\n", ansc, kase);
	}
	return 0;
}