能力值：
( LV4，RANK：50 )
在线值：
|
-
-
2 楼
注册机代码
作为习题，请修改打印出所有注册码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | using namespace std;
int table[8*9]={ //表格，根据调试时内存中数据所得
0,0,0,0,0,0,0,0,0, //no use
0,0,0,1,1,1,0,0,0,
0,0,0,1,1,1,0,0,0,
0,1,1,1,1,1,1,1,0,
0,1,1,1,3,1,1,1,0,
0,1,1,1,1,1,1,1,0,
0,0,0,1,1,1,0,0,0,
0,0,0,1,1,1,0,0,0
};
const int MAX=32;
int tablePath[MAX][8*9];
int serial[MAX];
bool searchLevel(int level);
//复制当前表格状态，以便修改后不影响回溯
void copyTableTo(int level)
{
if(level>=MAX) return; //最后一个禁止拷贝，不然就溢出了，当然，也可以给tablePath加一维
memcpy(tablePath[level], tablePath[level-1], 8*9*sizeof(int));
}
//用x匹配注册码中第level个数值（level从0开始）
//核心算法
bool doSearch(int level, int x)
{
int ecx=(x/4)%7+1;
int edx=((x/4)/7)%7+1;
int edi=x&3;
int offset=ecx+9*edx;
bool ok=false;
switch(edi) {
case 0:
if(tablePath[level][offset-9]==1
&& tablePath[level][offset-0x12]==3) {
serial[level]=x;
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset-9]=3;
tablePath[level+1][offset-0x12]=1;
ok=true;
}
break;
case 1:
if(tablePath[level][offset+1]==1
&& tablePath[level][offset+2]==3) {
serial[level]=x;
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset+1]=3;
tablePath[level+1][offset+2]=1;
ok=true;
}
break;
case 2:
if(tablePath[level][offset+9]==1
&& tablePath[level][offset+0x12]==3) {
serial[level]=x;
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset+9]=3;
tablePath[level+1][offset+0x12]=1;
ok=true;
}
break;
case 3:
if(tablePath[level][offset-1]==1
&& tablePath[level][offset-2]==3) {
serial[level]=x;
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset-1]=3;
tablePath[level+1][offset-2]=1;
ok=true;
}
break;
}
if(ok)
return searchLevel(level+1);
else
return false;
}
//搜索序列号第level个数值（level从0开始）
bool searchLevel(int level)
{
if(level>=MAX) return true;
cout<<"Searching on level: "<<level<<endl;
for(int x=0;x<=0xff;x++) {
if(doSearch(level, x))
return true;
}
cout<<"Failed on level:"<<level<<endl;
return false;
}
int main()
{
/* 我是据此发现x/7跟代码中HIGHDWORD的等价性的
unsigned long long m=0x92492493;
for(unsigned long long i=0;i<=0x3f;i++) {
unsigned long long r = m*i;
cout << i << ":" << (r>>32)/4 << ":" << i/28<< endl;
}
*/
memcpy(tablePath[0], table, 8*9*sizeof(int));
if(searchLevel(0)) {
cout<<"Serial found!\n";
//copy(serial, serial+32, ostream_iterator<int>((cout<<setw(2)<<setfill('0')<<setiosflags(ios::hex)), ""));
for(int i=0;i<MAX;i++) {
cout<<hex<<setw(2)<<setfill('0')<<serial[i];
}
}
return 0;
}
|
|
能力值：
( LV2，RANK：10 )
在线值：
|
-
-
3 楼
厉害
!!!是很晚了,应该休息了
|
能力值：
( LV15，RANK：2473 )
在线值：
|
-
-
4 楼
如果楼主用ida辅助分析的话就会少走一些弯路了，有些其实是vc提供的库函数
.text:00401171 call _isxdigit
...
.text:0040128A call _sscanf
...
还有这个游戏的名字叫“独立钻石”，网上可以搜一下
|
能力值：
( LV4，RANK：50 )
在线值：
|
-
-
5 楼
哦，原来是这样，我还以为你故意的，呵呵
机器上没装IDA，这个东西od没有办法搞定么？
是VC以源代码方式提供的？exe里似乎没有看到VC相关的dll
|
能力值：
( LV15，RANK：2473 )
在线值：
|
-
-
6 楼
如果od能解决所有问题，ida还能卖的出去吗
|
能力值：
![]()
(RANK：410 )
|
-
-
7 楼
是递归搜索吗？
|
能力值：
( LV4，RANK：50 )
在线值：
|
-
-
8 楼
恩，是递归，也是回溯，同时也是DFS
|
能力值：
![]()
(RANK：410 )
|
-
-
9 楼
oh.这就是传说的DFS。学习了。是个好方法。
不过得不到最优解吧。
|
能力值：
( LV4，RANK：50 )
在线值：
|
-
-
10 楼
恩……不知道你说的最优解是指什么？因为这里所有的解都是得到1000分，无所谓最优吧？
是指搜索速度么？
|
能力值：
![]()
(RANK：410 )
|
-
-
11 楼
恩，最少步数。你的算法已经简介高效的完成了任务。
我只是想了解有没有最优解的算法。
|
能力值：
( LV4，RANK：50 )
在线值：
|
-
-
12 楼
其实这个独立钻石游戏的步数显然是固定的，游戏每步移掉一个棋子，一共32个棋子，因此步数肯定是31步
他的算法还根据x&3限定了跳的方向，我不知道为什么
而且我怀疑他是否漏了一个检查，即检查原处是否有棋子，看这个if判断：
1 2 | if(tablePath[level][offset-9]==1 //被跳处是否有棋
&& tablePath[level][offset-0x12]==3) { //对面是否是空位
|
似乎还应该加上tablePath[level][offset]的判断
造成的影响就是有时候棋子会增加……-_-
对于真正的独立钻石游戏的搜索，我想可以通过下面两条来加快搜索速度：
1. 只搜索空位附近的棋子（前期应该可以剪掉很多搜索分支）
2. 用hash保存棋盘状态，防止重复搜索（类似DP，即动态规划）
你有兴趣的话可以做做：）
|
能力值：
![]()
(RANK：410 )
|
-
-
13 楼
根据网上查的关于“独钻”的资料，只剩一字的为大师，只剩一子且该子居中，则为天才。天才又根据步数分等。最早有人发现19步解法。后又发现18步的2种解法。
所以我猜想该crack应该是有很多种解法的，但最优解只有两种。这个crack没有仔细跟（我看的太慢，所以没跟），不知他做了什么限定没有。有空去研究下。
|
能力值：
( LV4，RANK：50 )
在线值：
|
-
-
14 楼
哦，原来真正的独钻是可以跳过多个棋子的……怪不得步数会不一样
|
能力值：
( LV15，RANK：2473 )
在线值：
|
-
-
15 楼
只有上下左右4个方向啊,为什么不可以限制方向？
应该是漏掉了这个检查
|
能力值：
( LV4，RANK：50 )
在线值：
|
-
-
16 楼
但是你的坐标是根据x得出来的阿
而任何一个坐标处的棋子应该可以有四个自由度把，你这样的话一个坐标上的棋子只能往一个方向跳了
|
能力值：
( LV15，RANK：2473 )
在线值：
|
-
-
17 楼
难道 &3不是表示4个自由度吗？
|
能力值：
( LV2，RANK：10 )
在线值：
|
-
-
18 楼
算法啊，头疼，头疼，我还是走爆爆的路吧，学不会啊
|
能力值：
( LV4，RANK：50 )
在线值：
|
-
-
19 楼
但是对于某个特定坐标上的棋子不是阿，始终是往x&3那个方向跳的，对么？
当然，也可以认为是特殊的限制条件，但是如果加上上面那个检查，很可能是无解的……
btw: 加上那个检查可以增加很多计算量，搜索算法需要做优化，我搜了很久都没搜完……
|
能力值：
![]()
(RANK：1060 )
|
-
-
20 楼
and 3d = and 11b 保留2bit，表示范围0~2^2-1=0-3=0 1 2 3，相当于mod 4, 四个方向
|
能力值：
( LV12，RANK：570 )
在线值：
|
-
-
21 楼
顶，我也下去破了一下。蛮有趣的，绕一个大弯子然后再……其乐无穷。作者写的真的很好，我顶。
|
能力值：
( LV4，RANK：50 )
在线值：
|
-
-
22 楼
哦，你说得对，是我搞错了，可以是从0-0xff的，方向信息已经包含在其中了。
另外给出针对ccfer本意的注册机（即加上棋子检查后）：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | using namespace std;
const int STEP=31;
const int SIZE=7;
int _table[SIZE*SIZE]={ //表格，根据调试时内存中数据所得
0,0,1,1,1,0,0,
0,0,1,1,1,0,0,
1,1,1,1,1,1,1,
1,1,1,3,1,1,1,
1,1,1,1,1,1,1,
0,0,1,1,1,0,0,
0,0,1,1,1,0,0
};
vector<int> table(_table, _table+SIZE*SIZE);
vector<int> tablePath[STEP+1];
map<vector<int>, bool> failedTables[STEP];
int serial[STEP];
bool searchLevel(int level);
//复制当前表格状态，以便修改后不影响回溯
void copyTableTo(int level)
{
tablePath[level]=tablePath[level-1];
}
//用x匹配注册码中第level个数值（level从0开始）
//核心算法
bool doSearch(int level, int pos)
{
int row=((pos/4)/SIZE)%SIZE;
int col=(pos/4)%SIZE;
int d=pos&3;
int offset=SIZE*row+col;
bool ok=false;
if(tablePath[level][offset]!=1) return false;
switch(d) {
case 0:
//jump up
if(row>2 && tablePath[level][offset-7]==1 && tablePath[level][offset-14]==3) {
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset-7]=3;
tablePath[level+1][offset-14]=1;
ok=true;
}
break;
//jump right
case 1:
if(col<5 && tablePath[level][offset+1]==1 && tablePath[level][offset+2]==3) {
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset+1]=3;
tablePath[level+1][offset+2]=1;
ok=true;
}
break;
case 2:
//jump down
if(row<5 &&tablePath[level][offset+7]==1 && tablePath[level][offset+14]==3) {
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset+7]=3;
tablePath[level+1][offset+14]=1;
ok=true;
}
break;
case 3:
//jump left
if(col>2 && tablePath[level][offset-1]==1 && tablePath[level][offset-2]==3) {
copyTableTo(level+1);
tablePath[level+1][offset]=3;
tablePath[level+1][offset-1]=3;
tablePath[level+1][offset-2]=1;
ok=true;
}
break;
}
if(ok) {
serial[level]=pos;
return searchLevel(level+1);
}
return false;
}
//搜索序列号第level个数值（level从0开始）
bool searchLevel(int level)
{
if(level>=STEP) return (tablePath[level][3*7+3]==1);
if(failedTables[level].find(tablePath[level])!=failedTables[level].end()) return false;
for(int pos=0;pos<0xff;pos++) {
if(doSearch(level, pos)) {
return true;
}
}
//纪录失败状态（包括因对称性而存在的等价状态），防止重复搜索
vector<int> tempTable(tablePath[level]);
failedTables[level][tempTable] = false;
for(int x=0;x<SIZE;x++)
for(int y=0;y<SIZE;y++)
tempTable[SIZE*x+y]=tablePath[level][SIZE*y+x];
failedTables[level][tempTable] = false;
for(int x=0;x<SIZE;x++)
for(int y=0;y<SIZE;y++)
tempTable[SIZE*x+y]=tablePath[level][SIZE*x+(6-y)];
failedTables[level][tempTable] = false;
for(int x=0;x<SIZE;x++)
for(int y=0;y<SIZE;y++)
tempTable[SIZE*x+y]=tablePath[level][SIZE*(6-x)+y];
failedTables[level][tempTable] = false;
for(int x=0;x<SIZE;x++)
for(int y=0;y<SIZE;y++)
tempTable[SIZE*x+y]=tablePath[level][SIZE*(6-y)+6-x];
failedTables[level][tempTable] = false;
return false;
}
int main()
{
tablePath[0]=table;
if(searchLevel(0)) {
cout<<"Serial found!\n";
for(int i=0;i<STEP;i++) {
cout<<hex<<setw(2)<<setfill('0')<<serial[i];
}
cout<<endl;
} else {
cout<<"No serial found...\n";
}
return 0;
}
|
|
能力值：
( LV2，RANK：10 )
在线值：
|
-
-
23 楼
OD 里面菜单 调试 - 加入库文件，把MFC或用到的DLL的 lib文件加进去就可以识别调用的函数名了
|
|
|
|
