首页
社区
课程
招聘
[讨论][第二阶段◇第一题]程序
发表于: 2008-10-19 19:52 15514

[讨论][第二阶段◇第一题]程序

2008-10-19 19:52
15514
贴一个自己的解法,思路很简单,就是以水平方向为X轴,60度那条斜线为Y轴,确定一个菱形块的位置,再对菱形块中的两个三角形按上下进行区分,确定好坐标后,对整个72格的空间进行递归搜索,最后对搜索出来的结果进行检查,发现是对称的就删除其中的一个。程序最终找到5885个结果。程序写的有点乱,期待大牛们的作品。
//DRAW 定义为1时可以在屏幕上输出彩色的解决方案
#define DRAW 0
#include "windows.h"
#include "wincon.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"

const int zh[12] = {0, 1, 6, 7, 2, 3, 8, 9, 4, 5, 10, 11};
const int cs[8] = {11, 13, 13, 11, 9, 7, 5, 3};
const int gs[13] = {0, 1, 4, 16, 22, 34, 40, 52, 64, 70, 76, 88, 94};
const short int color[12] = {1,2,3,4,5,6,9,10,11,12,13,14};
const unsigned int b[94][6] = 
{
	{0x000001,0x010000,0x010001,0x000100,0x000101,0x010100},
	{0x010000,0x010001,0x020000,0x000101,0x010100,0x010101},
	{0x010001,0x000100,0x000101,0x010100,0x010101,0x000200},
	{0x010001,0x000101,0x010100,0x010101,0x020100,0x010200},
	{0x020001,0x000100,0x000101,0x010100,0x010101,0x020100},
	{0x000001,0x000100,0x000101,0x000200,0x000201,0x010200},
	{0x010001,0x020000,0x000101,0x010100,0x000200,0x000201},
	{0x000001,0x010000,0x010001,0x020000,0x020001,0x000100},
	{0x000001,0x010000,0x010001,0x010100,0x010101,0x010200},
	{0x020000,0x020001,0x010101,0x020100,0x000201,0x010200},
	{0x010000,0x010001,0x010100,0x010101,0x000201,0x010200},
	{0x020001,0x010101,0x020100,0x000200,0x000201,0x010200},
	{0x000001,0x000100,0x000101,0x010100,0x010101,0x020100},
	{0x000001,0x010000,0x000100,0x000101,0x000200,0x000201},
	{0x010001,0x020000,0x020001,0x000101,0x010100,0x000200},
	{0x000001,0x010000,0x010001,0x020000,0x020001,0x020100},
	{0x010000,0x010001,0x000100,0x000101,0x010100,0x010101},
	{0x000001,0x010001,0x000100,0x000101,0x010100,0x000200},
	{0x010001,0x020000,0x000101,0x010100,0x010101,0x020100},
	{0x000000,0x000001,0x010000,0x010001,0x000100,0x000101},
	{0x010001,0x000101,0x010100,0x010101,0x000200,0x010200},
	{0x000001,0x010000,0x010001,0x020000,0x000101,0x010100},
	{0x000000,0x000001,0x010000,0x010001,0x000101,0x010100},
	{0x010001,0x010100,0x010101,0x000200,0x000201,0x010200},
	{0x000001,0x010001,0x020000,0x000100,0x000101,0x010100},
	{0x000001,0x010000,0x000100,0x000101,0x010100,0x010101},
	{0x000001,0x010000,0x010001,0x000100,0x000101,0x000200},
	{0x010001,0x020000,0x020001,0x000101,0x010100,0x020100},
	{0x000000,0x000001,0x010001,0x000100,0x000101,0x010100},
	{0x010001,0x000101,0x010100,0x000200,0x000201,0x010200},
	{0x000001,0x010000,0x010001,0x020000,0x000100,0x000101},
	{0x000001,0x010000,0x010001,0x000100,0x010100,0x010101},
	{0x000001,0x010000,0x010001,0x000101,0x010100,0x000200},
	{0x020000,0x020001,0x000101,0x010100,0x010101,0x020100},
	{0x000000,0x000001,0x000100,0x000101,0x010100,0x010101},
	{0x010001,0x000101,0x010100,0x000200,0x000201,0x000300},
	{0x010001,0x020000,0x020001,0x030000,0x000101,0x010100},
	{0x000000,0x000001,0x010000,0x010001,0x010100,0x010101},
	{0x010001,0x010100,0x010101,0x000201,0x010200,0x000300},
	{0x020001,0x030000,0x000101,0x010100,0x010101,0x020100},
	{0x010000,0x010001,0x020000,0x000100,0x000101,0x010100},
	{0x000001,0x010001,0x000100,0x000101,0x010100,0x010101},
	{0x000001,0x010000,0x000100,0x000101,0x010100,0x000200},
	{0x010001,0x020000,0x020001,0x000101,0x010100,0x010101},
	{0x000000,0x000001,0x010000,0x010001,0x000100,0x010100},
	{0x010001,0x000101,0x010100,0x010101,0x000201,0x010200},
	{0x010000,0x010001,0x000100,0x000101,0x010100,0x000200},
	{0x010001,0x020001,0x000101,0x010100,0x010101,0x020100},
	{0x000000,0x000001,0x010000,0x000100,0x000101,0x010100},
	{0x010001,0x000101,0x010100,0x010101,0x000200,0x000201},
	{0x000001,0x010000,0x010001,0x020000,0x000100,0x010100},
	{0x000001,0x010000,0x010001,0x000101,0x010100,0x010101},
	{0x010001,0x020000,0x000100,0x000101,0x010100,0x010101},
	{0x000001,0x000100,0x000101,0x010100,0x010101,0x000200},
	{0x010001,0x020000,0x000101,0x010100,0x010101,0x010200},
	{0x010000,0x010001,0x020000,0x020001,0x000101,0x010100},
	{0x010001,0x000100,0x000101,0x010100,0x010101,0x010200},
	{0x010001,0x010100,0x010101,0x020100,0x000201,0x010200},
	{0x010000,0x010001,0x000101,0x010100,0x010101,0x000200},
	{0x020001,0x000101,0x010100,0x010101,0x020100,0x010200},
	{0x010000,0x010001,0x000101,0x010100,0x010101,0x020100},
	{0x010001,0x000100,0x000101,0x010100,0x000200,0x000201},
	{0x010001,0x000101,0x010100,0x010101,0x020100,0x000200},
	{0x000001,0x010000,0x010001,0x020000,0x010100,0x010101},
	{0x010001,0x020000,0x020001,0x000100,0x000101,0x010100},
	{0x000001,0x000100,0x000101,0x010100,0x010101,0x010200},
	{0x010001,0x020000,0x010100,0x010101,0x000201,0x010200},
	{0x010000,0x010001,0x000101,0x010100,0x000200,0x000201},
	{0x020001,0x000101,0x010100,0x010101,0x020100,0x000200},
	{0x000001,0x010000,0x010001,0x010100,0x010101,0x020100},
	{0x010001,0x000100,0x000101,0x010100,0x010101,0x020100},
	{0x000001,0x000100,0x000101,0x010100,0x000200,0x000201},
	{0x010001,0x020000,0x000101,0x010100,0x010101,0x000200},
	{0x000001,0x010000,0x010001,0x020000,0x020001,0x010100},
	{0x010000,0x010001,0x000101,0x010100,0x010101,0x010200},
	{0x020001,0x010100,0x010101,0x020100,0x000201,0x010200},
	{0x010001,0x000101,0x010100,0x010101,0x020100,0x020101},
	{0x000000,0x000001,0x010000,0x000100,0x000101,0x000200},
	{0x020001,0x010101,0x020100,0x020101,0x000201,0x010200},
	{0x000000,0x000001,0x010000,0x010001,0x020000,0x010100},
	{0x010001,0x010100,0x010101,0x000201,0x010200,0x010201},
	{0x010001,0x020000,0x000100,0x000101,0x010100,0x000200},
	{0x010001,0x000101,0x010100,0x010101,0x010200,0x010201},
	{0x010000,0x010001,0x020000,0x000101,0x010100,0x000200},
	{0x020001,0x000101,0x010100,0x010101,0x020100,0x020101},
	{0x000000,0x000001,0x000100,0x000101,0x010100,0x000200},
	{0x020001,0x010101,0x020100,0x000201,0x010200,0x010201},
	{0x000000,0x000001,0x010000,0x010001,0x020000,0x000100},
	{0x000000,0x000001,0x010000,0x010001,0x020000,0x020001},
	{0x000001,0x000100,0x000101,0x000200,0x000201,0x000300},
	{0x020001,0x030000,0x010101,0x020100,0x000201,0x010200},
	{0x000000,0x000001,0x000100,0x000101,0x000200,0x000201},
	{0x020001,0x010101,0x020100,0x000201,0x010200,0x000300},
	{0x000001,0x010000,0x010001,0x020000,0x020001,0x030000}
};
const unsigned int qp[72] = 
{
	0x010001,0x020000,0x020001,0x030000,0x030001,0x040000,
	0x040001,0x050000,0x050001,0x060000,0x060001,0x000101,
	0x010100,0x010101,0x020100,0x020101,0x030100,0x030101,
	0x040100,0x040101,0x050100,0x050101,0x060100,0x060101,
	0x000200,0x000201,0x010200,0x010201,0x020200,0x020201,
	0x030200,0x030201,0x040200,0x040201,0x050200,0x050201,
	0x060200,0x000300,0x000301,0x010300,0x010301,0x020300,
	0x020301,0x030300,0x030301,0x040300,0x040301,0x050300,
	0x000400,0x000401,0x010400,0x010401,0x020400,0x020401,
	0x030400,0x030401,0x040400,0x000500,0x000501,0x010500,
	0x010501,0x020500,0x020501,0x030500,0x000600,0x000601,
	0x010600,0x010601,0x020600,0x000700,0x000701,0x010700
};
unsigned char tb[12000][72];
unsigned char space[16][16][2];//放置棋盘的空间,各偏移4
int jl1[12];//哪个形状已被使用
int jl2[12];//该形状对应的翻转和旋转后状态
int m;//用了几个形状
int w;//找到的解法个数

void search(int n)//n为目前搜索的棋盘位置
{
	int i, j, k;
	int x, y, z;

	while (space[((qp[n]>>16)&0xFF)+4][((qp[n]>>8)&0xFF)+4][qp[n]&0xFF] != 12) n = n+1;//找到下一个空位
	x = ((qp[n]>>16)&0xFF)+4;
	y = ((qp[n]>> 8)&0xFF)+4;
	for(i=0; i<12; i++)
	{
		if (jl1[i]) continue;//该形状已被使用
		for(j=gs[i]; j<gs[i+1]; j++)
		{
			if ((qp[n]&0xFF) != (b[j][0]&0xFF)) continue;
			for(k=1; k<6; k++)
			{
				if (space[x+((b[j][k]>>16)&0xFF)-((b[j][0]>>16)&0xFF)][y+((b[j][k]>>8)&0xFF)-((b[j][0]>>8)&0xFF)][b[j][k]&0xFF] != 12) break;
			}
			if (k == 6)//找到一个形状可以放下
			{
				for(k=0; k<6; k++) space[x+((b[j][k]>>16)&0xFF)-((b[j][0]>>16)&0xFF)][y+((b[j][k]>>8)&0xFF)-((b[j][0]>>8)&0xFF)][b[j][k]&0xFF] = i;
				jl1[i] = 1;
				jl2[m] = j;
				m = m+1;
				if (m == 12)//找到一个解法
				{
					for(z=0; z<72; z++) tb[w][z] = zh[space[((qp[z]>>16)&0xFF)+4][((qp[z]>>8)&0xFF)+4][qp[z]&0xFF]];
					w = w+1;
					m = m-1;
					for(k=0; k<6; k++) space[x+((b[j][k]>>16)&0xFF)-((b[j][0]>>16)&0xFF)][y+((b[j][k]>>8)&0xFF)-((b[j][0]>>8)&0xFF)][b[j][k]&0xFF] = 12;
					jl1[i] = 0;
					return;
				}
				else
				{
					search(n+1);
					m = m-1;
					for(k=0; k<6; k++) space[x+((b[j][k]>>16)&0xFF)-((b[j][0]>>16)&0xFF)][y+((b[j][k]>>8)&0xFF)-((b[j][0]>>8)&0xFF)][b[j][k]&0xFF] = 12;
					jl1[i] = 0;
				}
			}
		}
	}
}

int main()
{
	int i, j, k, l, r, v;
	unsigned char tt[72];
	HANDLE h;
	DWORD ut;
	FILE *fp;

	h = GetStdHandle(STD_OUTPUT_HANDLE);
	for(i=0; i<16; i++)
	{
		for(j=0; j<16; j++)
		{
			space[i][j][0] = 0;
			space[i][j][1] = 0;
		}
	}
	for(i=0; i<72; i++) space[((qp[i]>>16)&0xFF)+4][((qp[i]>>8)&0xFF)+4][qp[i]&0xFF] = 12;
	for(i=0; i<12; i++) jl1[i] = 0;
	//开始搜索
	ut = GetTickCount();
	w = m = 0;
	search(0);
	//对结果去掉重复的对称方案
	for(i=0; i<w; i++)
	{
		if (tb[i][0] == 12) continue;
		r = 0;
		for(k=0; k<8; k++)
		{
			for(l=0; l<cs[k]; l++)
			{
				tt[r+l] = tb[i][r+cs[k]-1-l];
			}
			r += cs[k];
		}
		for(j=i+1; j<w; j++)
		{
			if (tb[j][0] == 12) continue;
			if (memcmp(tb[j], tt, 72) == 0) tb[j][0] = 12;
		}
	}
	printf("使用时间:%dms\n", GetTickCount()-ut);
	//要输入到屏幕上看直观方案吗?
	if (DRAW)
	{
		for(l=0; l<w; l++)
		{
			if (tb[l][0] == 12) continue;
			r = 72;
			for(i=7; i>=0; i--)
			{
				for(j=0; j<(13-cs[i])/2; j++) printf(" ");
				for(k=0,j=r-cs[i]; j<r; j++,k++)
				{
					SetConsoleTextAttribute(h, color[tb[l][j]]);
					if (i>1)
					{
						if (k&1)
							printf("▼");
						else
							printf("▲");
					}
					else
					{
						if (k&1)
							printf("▲");
						else
							printf("▼");
					}
					SetConsoleTextAttribute(h, 0x7);
				}
				printf("\n");
				r -= cs[i];
			}
			printf("\n");
		}
	}
	//输出结果到文本文件
	fp = fopen("out.txt", "wt");
	for(l=0; l<w; l++)
	{
		if (tb[l][0] == 12) continue;
		r = 72; v = 11;
		for(i=7; i>=0; i--)
		{
			if (i == 1) v = v+1;
			for(j=0; j<v; j++) fprintf(fp, " ");
			for(k=0,j=r-cs[i]; j<r; j++,k++)
			{
				if (i>1)
				{
					if (k&1)
					{
						fprintf(fp, "%1X%1X%1X", tb[l][j], tb[l][j], tb[l][j]);
					}
					else
					{
						fprintf(fp, "%1X", tb[l][j]);
					}
				}
				else
				{
					if (k&1)
					{
						fprintf(fp, "%1X", tb[l][j]);
					}
					else
					{
						fprintf(fp, "%1X%1X%1X", tb[l][j], tb[l][j], tb[l][j]);
					}
				}
			}
			if (i>1)
				v = v-1;
			else
				v = v+1;
			fprintf(fp, "\n");
			for(j=0; j<v; j++) fprintf(fp, " ");
			for(k=0,j=r-cs[i]; j<r; j++,k++)
			{
				if (i>1)
				{
					if (k&1)
					{
						fprintf(fp, "%1X", tb[l][j]);
					}
					else
					{
						fprintf(fp, "%1X%1X%1X", tb[l][j], tb[l][j], tb[l][j]);
					}
				}
				else
				{
					if (k&1)
					{
						fprintf(fp, "%1X%1X%1X", tb[l][j], tb[l][j], tb[l][j]);
					}
					else
					{
						fprintf(fp, "%1X", tb[l][j]);
					}
				}
			}
			if (i>1)
				v = v-1;
			else
				v = v+1;
			fprintf(fp, "\n");
			r -= cs[i];
		}
		fprintf(fp, "\n");
	}
	fclose(fp);
}

[课程]Linux pwn 探索篇!

收藏
免费 7
支持
分享
最新回复 (49)
雪    币: 398
活跃值: (343)
能力值: (RANK:650 )
在线值:
发帖
回帖
粉丝
2
此贴不能不顶啊
这就素标准答案啊
2008-10-19 20:01
0
雪    币: 233
活跃值: (15)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
3
顶,学习中!!!
2008-10-19 20:09
0
雪    币: 207
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
4
BCB6上測了下
2008-10-19 20:12
0
雪    币: 740
活跃值: (952)
能力值: ( LV9,RANK:160 )
在线值:
发帖
回帖
粉丝
5
不能不顶的算法大牛
2008-10-19 21:24
0
雪    币: 7309
活跃值: (3778)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
6
这个就是传说中的15秒答案啊,只能说膜拜
2008-10-19 21:24
0
雪    币: 334
活跃值: (22)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
7
来晚了 ,学习学习......
2008-10-19 21:28
0
雪    币: 221
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
8
牛,顶一个。。
2008-10-19 21:42
0
雪    币: 479
活跃值: (25)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
9
Y轴设的巧妙,牛。。。
2008-10-19 22:05
0
雪    币: 8209
活跃值: (4458)
能力值: ( LV15,RANK:2459 )
在线值:
发帖
回帖
粉丝
10
学习
y轴90度别扭死我了
2008-10-19 22:07
0
雪    币: 101
活跃值: (12)
能力值: ( LV12,RANK:210 )
在线值:
发帖
回帖
粉丝
11
建两个棋盘的方法, 学习了,
我电脑上6秒跑完, 牛
2008-10-20 01:13
0
雪    币: 347
活跃值: (25)
能力值: ( LV9,RANK:420 )
在线值:
发帖
回帖
粉丝
12
我是过来膜拜的
2008-10-20 02:24
0
雪    币: 423
活跃值: (11)
能力值: ( LV9,RANK:230 )
在线值:
发帖
回帖
粉丝
13
又一头大水牛,潜水很深的大牛!!!

考试后细细体会。
2008-10-20 08:06
0
雪    币: 136
活跃值: (20)
能力值: ( LV10,RANK:170 )
在线值:
发帖
回帖
粉丝
14
膜拜!
太精彩了。
2008-10-20 08:22
0
雪    币: 446
活跃值: (723)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
15
看到源码了,太牛了
2008-10-20 09:38
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
果然是硬编码的啊。。。
我卡在旋转那就放弃了。。。
2008-10-20 09:43
0
雪    币: 2316
活跃值: (129)
能力值: (RANK:410 )
在线值:
发帖
回帖
粉丝
17
膜拜,学习。
2008-10-20 10:58
0
雪    币: 993
活跃值: (442)
能力值: ( LV12,RANK:403 )
在线值:
发帖
回帖
粉丝
18
感谢楼上的各位大牛们。你们才是我学习的目标。
2008-10-20 12:22
0
雪    币: 7309
活跃值: (3778)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
19
向LS学习如何使用马甲
2008-10-20 12:31
0
雪    币: 993
活跃值: (442)
能力值: ( LV12,RANK:403 )
在线值:
发帖
回帖
粉丝
20
呵呵,我的ID只有这一个,06年注册的,在第一阶段第二题的注册机题目里问过很初级的问题,还是楼上的海风大牛给的回答 感谢海风大牛
2008-10-20 12:44
0
雪    币: 216
活跃值: (26)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
21
曾经想过用硬编码,感觉太麻烦,就放弃了............
学习楼主的惊人的毅力...........
2008-10-20 12:45
0
雪    币: 993
活跃值: (442)
能力值: ( LV12,RANK:403 )
在线值:
发帖
回帖
粉丝
22
没有惊人的毅力,呵呵,纯粹是机器干的活,你只需要给出最原始的十二块的坐标就行,
剩下的写个小转换程序让机器自己替你旋转和翻转,完成后对坐标进行偏移修正就行,
最后统一输出到一个数组就完成你的预编码过程了。
2008-10-20 12:56
0
雪    币: 268
活跃值: (95)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
23
膜拜,学习。
2008-10-20 13:01
0
雪    币: 255
活跃值: (49)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
24
厉害 顶一下
2008-10-20 13:28
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
25
求旋转和翻转代码
2008-10-20 13:48
0
游客
登录 | 注册 方可回帖
返回
//