mirror of https://github.com/dnomd343/HRD_Game
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
644 lines
22 KiB
644 lines
22 KiB
#include <iostream>
|
|
#include <vector>
|
|
#include <string>
|
|
#include <list>
|
|
#include <fstream>
|
|
using namespace std;
|
|
|
|
ifstream File_Input;
|
|
ofstream File_Output;
|
|
const unsigned char Up = 1, Down = 2, Left = 3, Right = 4;
|
|
|
|
//用于寻找下一布局
|
|
struct block_struct {
|
|
unsigned char address; //0~19
|
|
unsigned char style; //0:2*2 1:2*1 2:1*2 3:1*1
|
|
};
|
|
unsigned char table[20]; //0~9:block[?] 0xA:space 0xFF:empty
|
|
unsigned char space[2]; //space[0~1]的位置
|
|
struct block_struct block[10]; //0:2*2 1~5:1*2,2*1 6~9:1*1
|
|
|
|
bool quick; //仅计算最短步骤
|
|
int Solution_num_quick;
|
|
vector <unsigned int> Source_quick; //父布局编号
|
|
vector <unsigned int> Solution_quick; //最短路径
|
|
|
|
//用于绘制整个队列树
|
|
unsigned int Now_Move; //目前正在进行计算的布局编号
|
|
list <unsigned int> int_list; //空列表
|
|
vector <unsigned int> int_vector; //空vector
|
|
list <unsigned int> Hash[0x10000]; //哈希索引表
|
|
vector <unsigned int> List; //所有情况的队列
|
|
vector <unsigned int> Layer_Num; //所在层的编号
|
|
vector <unsigned int> Layer_Index; //层中所属的编号
|
|
vector <list <unsigned int> > Source; //父布局编号
|
|
vector <vector <unsigned int> > Layer; //分层
|
|
vector <vector <vector <unsigned int> > > Layer_Next; //分层链接
|
|
|
|
//布局的基本参数
|
|
int group_size; //整个队列组的大小
|
|
int min_steps; //解的最少步骤
|
|
int farthest_steps; //最远布局的步数
|
|
vector <unsigned int> Solutions; //所有解
|
|
vector <unsigned int> Solutions_steps; //所有解的最少步
|
|
vector <unsigned int> min_Solutions; //所有最少步解
|
|
vector <unsigned int> farthest_cases; //所有最远的布局
|
|
//vector <unsigned int> solution_path; //最少步解法
|
|
|
|
void debug();
|
|
void Find_All_Case();
|
|
void Data_Output(string File_name);
|
|
void Split_Layer();
|
|
unsigned int Change_int (char str[8]);
|
|
string Change_str (unsigned int dat);
|
|
void Output_Graph (unsigned int Code);
|
|
void Analyse_Code (unsigned int Code);
|
|
void Add_Case (unsigned int Code);
|
|
void Calculate (unsigned int Start_Code);
|
|
void Date_Back_quick (int num);
|
|
void Calculate_quick (unsigned int Start_Code);
|
|
bool Check (unsigned int Code);
|
|
unsigned int Get_Code();
|
|
void Find_Next();
|
|
bool Check_Empty (unsigned char address,unsigned char dir,unsigned char num);
|
|
void Move_Block (unsigned char num,unsigned char dir_1,unsigned char dir_2);
|
|
void Fill_Block (unsigned char addr, unsigned char style, unsigned char filler);
|
|
vector <unsigned int> Search_Path (unsigned int target_num);
|
|
void Analyse_Case (unsigned int Start_Code);
|
|
|
|
int main(int argc, char* argv[]) {
|
|
unsigned int Code, i;
|
|
string File_name, Parameter;
|
|
cout << "HRD-Engine by Dnomd343" << endl;
|
|
if (argc == 3) {
|
|
Parameter = argv[1];
|
|
Code = Change_int(argv[2]);
|
|
if (Check(Code) == false) {cout << "Code Error" << endl; return 0;}
|
|
File_name = Change_str(Code) + ".txt";
|
|
if (Parameter == "-q") {
|
|
cout << "Quick Calculate Mode." << endl;
|
|
cout << "Code: " << Change_str(Code) << endl;
|
|
cout << "Data Save at " << File_name << endl;
|
|
quick = true;
|
|
Calculate_quick(Code);
|
|
Date_Back_quick(Solution_num_quick);
|
|
File_Output.open(File_name.c_str());
|
|
if (Solution_quick.size() == 0) {
|
|
File_Output << "No Solution" << endl;
|
|
} else {
|
|
File_Output << Solution_quick.size() - 1 << endl;
|
|
}
|
|
for (i = 0; i < Solution_quick.size(); i++) {
|
|
File_Output << Change_str(Solution_quick[i]) << endl;
|
|
}
|
|
File_Output.close();
|
|
} else if (Parameter == "-a") {
|
|
cout << "All Calculate Mode." << endl;
|
|
cout << "Code: " << Change_str(Code) << endl;
|
|
cout << "Data Save at " << File_name << endl;
|
|
quick = false;
|
|
Analyse_Case(Code);
|
|
Data_Output(File_name);
|
|
} else {
|
|
cout << "Parameter Error" << endl;
|
|
}
|
|
} else {
|
|
cout << "Usage: [HRD-Engine.exe] [-q]/[-a] Code" << endl;
|
|
cout << "-q: Quick Calculate Mode" << endl << "-a: All Calculate Mode" << endl;
|
|
cout << "Such as 'HRD-Engine.exe -q 4FEA134'" << endl << " or 'HRD-Engine.exe -a 1A9BF0C'" << endl;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
void Analyse_Case (unsigned int Start_Code) { //对一个布局进行分析
|
|
unsigned int i, first_solution;
|
|
if (Check(Start_Code) == false) {return;} //若输入编码无效则退出
|
|
Calculate(Start_Code); //通过计算建立队列表
|
|
group_size = List.size(); //整个队列树大小
|
|
min_steps = -1;
|
|
farthest_steps = -1;
|
|
Solutions.clear();
|
|
Solutions_steps.clear();
|
|
min_Solutions.clear();
|
|
farthest_cases.clear();
|
|
//solution_path.clear();
|
|
bool get_it = false;
|
|
for (i = 0; i < List.size(); i++) { //遍历队列中所有元素
|
|
Analyse_Code(List[i]);
|
|
if (block[0].address == 13) { //若当前布局为有效解
|
|
if (get_it == false){
|
|
min_steps = Layer_Num[i]; //第一个找到的解为最少步解
|
|
first_solution = i;
|
|
get_it = true;
|
|
}
|
|
Solutions.push_back(List[i]); //将找到的有效解加入解集中
|
|
Solutions_steps.push_back(Layer_Num[i]);
|
|
if (Layer_Num[i] == min_steps) {
|
|
min_Solutions.push_back(List[i]); //将找到的最小步有效解加入最小步解集中
|
|
}
|
|
}
|
|
}
|
|
farthest_steps = Layer_Num[Layer_Num.size() - 1]; //计算最远布局的步数
|
|
for (i = Layer_Num.size() - 1; i > 0; i--) { //找到所有最远的布局
|
|
if(Layer_Num[i] != farthest_steps) {break;}
|
|
farthest_cases.push_back(List[i]);
|
|
}
|
|
//if (min_steps != -1) {solution_path = Search_Path(first_solution);}
|
|
}
|
|
|
|
void Split_Layer() {
|
|
vector <vector <unsigned int> > temp;
|
|
int i, num, index;
|
|
num = -1;
|
|
index = 0;
|
|
for (i = 0; i < Layer_Num.size(); i++) {
|
|
if (Layer_Num[i] != num) {
|
|
Layer.push_back(int_vector);
|
|
Layer_Next.push_back(temp);
|
|
num = Layer_Num[i];
|
|
index = 0;
|
|
}
|
|
Layer_Index.push_back(index);
|
|
index++;
|
|
Layer[num].push_back(List[i]);
|
|
Layer_Next[num].push_back(int_vector);
|
|
}
|
|
|
|
list <unsigned int>::iterator poi;
|
|
for (i = 1; i < List.size(); i++) {
|
|
poi = Source[i].begin();
|
|
while (poi != Source[i].end()) {
|
|
Layer_Next[Layer_Num[*poi]][Layer_Index[*poi]].push_back(Layer_Index[i]);
|
|
++poi;
|
|
}
|
|
}
|
|
}
|
|
|
|
vector <unsigned int> Search_Path (unsigned int target_num) { //搜索到达目标布局的一条最短路径 返回vector类
|
|
vector <unsigned int> path;
|
|
int temp = -1;
|
|
path.push_back(target_num); //路径中加入目标布局
|
|
while (temp != 0) {
|
|
temp = path[path.size() - 1];
|
|
path.push_back(*Source[temp].begin());
|
|
}
|
|
path.pop_back(); //去掉重复的根布局
|
|
temp = path.size() / 2; //反置整个路径
|
|
for (int i = 0; i < temp; i++) {
|
|
swap(path[i], path[path.size() - i - 1]);
|
|
}
|
|
for (int i = 0; i < path.size(); i++){ //将序号改成布局的编码
|
|
path[i] = List[path[i]];
|
|
}
|
|
return path;
|
|
}
|
|
|
|
void Date_Back_quick (int num) {
|
|
if (num == -1) {return;}
|
|
Solution_quick.push_back(List[num]);
|
|
if (num == 0) {return;}
|
|
while (Source_quick[num] != 0) {
|
|
num = Source_quick[num];
|
|
Solution_quick.push_back(List[num]);
|
|
}
|
|
Solution_quick.push_back(List[0]);
|
|
unsigned int i;
|
|
for (i = 0; i < Solution_quick.size() / 2 ; i++) {
|
|
swap(Solution_quick[i],Solution_quick[Solution_quick.size() - i - 1]);
|
|
}
|
|
}
|
|
|
|
void Calculate_quick (unsigned int Start_Code) { //启动计算引擎
|
|
unsigned int i;
|
|
for (i = 0; i <= 0xFFFF; i++) {Hash[i].clear();} //初始化
|
|
List.clear();
|
|
Source_quick.clear();
|
|
Solution_num_quick = -1;
|
|
Hash[(Start_Code>>4) & 0xFFFF].push_back(0); //加入初始布局
|
|
List.push_back(Start_Code);
|
|
Source_quick.push_back(0);
|
|
Now_Move = 0; //搜索目标指向根节点
|
|
while (Now_Move != List.size()) { //进行广度优先搜索
|
|
Analyse_Code(List[Now_Move]); //解析目标布局
|
|
if (block[0].address == 13) {
|
|
Solution_num_quick = Now_Move;
|
|
return;
|
|
}
|
|
Find_Next(); //根据解析结果搜索所有子布局
|
|
Now_Move++;
|
|
}
|
|
}
|
|
|
|
void Calculate (unsigned int Start_Code) { //启动计算引擎
|
|
unsigned int i;
|
|
for (i = 0; i <= 0xFFFF; i++) {Hash[i].clear();} //初始化
|
|
List.clear();
|
|
Layer_Num.clear();
|
|
Source.clear();
|
|
Hash[(Start_Code>>4) & 0xFFFF].push_back(0); //加入初始布局
|
|
List.push_back(Start_Code);
|
|
Layer_Num.push_back(0);
|
|
Source.push_back(int_list);
|
|
Now_Move = 0; //搜索目标指向根节点
|
|
while (Now_Move != List.size()) { //进行广度优先搜索
|
|
Analyse_Code(List[Now_Move]); //解析目标布局
|
|
Find_Next(); //根据解析结果搜索所有子布局
|
|
Now_Move++;
|
|
}
|
|
Split_Layer();
|
|
}
|
|
|
|
void Add_Case (unsigned int Code) { //将计算结果加入队列
|
|
list <unsigned int>::iterator poi; //定义迭代器
|
|
poi = Hash[(Code>>4) & 0xFFFF].begin(); //设置poi为索引表的起始点
|
|
while (poi != Hash[(Code>>4) & 0xFFFF].end()) { //遍历索引表
|
|
if (Code == List[*poi]) { //若发现重复
|
|
if (quick == true) {return;}
|
|
if ((Layer_Num[*poi] - Layer_Num[Now_Move]) == 1) { //若高一层
|
|
Source[*poi].push_back(Now_Move); //加入父节点列表
|
|
}
|
|
return; //重复 退出
|
|
}
|
|
++poi;
|
|
}
|
|
Hash[(Code>>4) & 0xFFFF].push_back(List.size()); //将计算结果添加至索引表
|
|
List.push_back(Code); //将计算结果加入队列
|
|
if (quick == false) {
|
|
Layer_Num.push_back(Layer_Num[Now_Move] + 1); //添加对应的层数
|
|
Source.push_back(int_list); //初始化其父节点列表
|
|
Source[Source.size()-1].push_back(Now_Move); //将正在进行搜索的布局添加为父节点
|
|
} else {
|
|
Source_quick.push_back(Now_Move); //将正在进行搜索的布局添加为父布局
|
|
}
|
|
}
|
|
|
|
void Fill_Block (unsigned char addr, unsigned char style, unsigned char filler) { //用指定内容填充table中指定的位置
|
|
if (style == 0) {table[addr] = table[addr + 1] = table[addr + 4] = table[addr + 5] = filler;} //2*2
|
|
else if (style == 1) {table[addr] = table[addr + 1] = filler;} //2*1
|
|
else if (style == 2) {table[addr] = table[addr + 4] = filler;} //1*2
|
|
else if (style == 3) {table[addr] = filler;} //1*1
|
|
}
|
|
|
|
void Move_Block (unsigned char num, unsigned char dir_1, unsigned char dir_2) { //按要求移动块并将移动后的编码传给Add_Case
|
|
unsigned char i, addr, addr_bak;
|
|
addr = block[num].address;
|
|
addr_bak = addr;
|
|
|
|
if (dir_1 == Up) {addr -= 4;} //第一次移动
|
|
else if (dir_1==Down) {addr += 4;}
|
|
else if (dir_1==Left) {addr--;}
|
|
else if (dir_1==Right) {addr++;}
|
|
if (dir_2 == Up) {addr -= 4;} //第二次移动
|
|
else if (dir_2 == Down) {addr += 4;}
|
|
else if (dir_2 == Left) {addr--;}
|
|
else if (dir_2 == Right) {addr++;}
|
|
|
|
Fill_Block(addr_bak, block[num].style, 0xA); //修改 table为移动后的状态
|
|
Fill_Block(addr, block[num].style, num);
|
|
block[num].address = addr;
|
|
|
|
Add_Case(Get_Code()); //生成编码并赋予Add_Case
|
|
|
|
block[num].address = addr_bak;
|
|
Fill_Block(addr, block[num].style, 0xA); //还原 table原来的状态
|
|
Fill_Block(addr_bak, block[num].style, num);
|
|
}
|
|
|
|
void Find_Next() { //寻找所有移动的方式并提交给Move_Block
|
|
bool Can_Move[10];
|
|
unsigned char i, addr;
|
|
for (i = 0; i < 10; i++) {Can_Move[i] = false;}
|
|
for (i = 0; i <= 1; i++) { //寻找位于空格周围的所有块
|
|
addr = space[i];
|
|
if (addr > 3)
|
|
if (table[addr - 4] != 0xA) {Can_Move[table[addr - 4]] = true;}
|
|
if (addr < 16)
|
|
if (table[addr + 4] != 0xA) {Can_Move[table[addr + 4]] = true;}
|
|
if (addr % 4 != 0)
|
|
if (table[addr - 1] != 0xA) {Can_Move[table[addr - 1]] = true;}
|
|
if (addr % 4 != 3) {
|
|
if (table[addr + 1] != 0xA) {Can_Move[table[addr + 1]] = true;}}
|
|
}
|
|
|
|
for (i = 0; i <= 9; i++) {
|
|
if (Can_Move[i] == true) { //若该块可能可以移动
|
|
addr = block[i].address;
|
|
if (block[i].style == 0) { //2*2
|
|
if ((Check_Empty(addr, Up, 1) == true) &&
|
|
(Check_Empty(addr + 1,Up, 1) == true)) {Move_Block(i, Up, 0);}
|
|
|
|
if ((Check_Empty(addr, Down, 2) == true) &&
|
|
(Check_Empty(addr + 1,Down, 2) == true)) {Move_Block(i, Down, 0);}
|
|
|
|
if ((Check_Empty(addr, Left, 1) == true) &&
|
|
(Check_Empty(addr + 4, Left, 1) == true)) {Move_Block(i, Left, 0);}
|
|
|
|
if ((Check_Empty(addr, Right, 2) == true) &&
|
|
(Check_Empty(addr + 4, Right, 2) == true)) {Move_Block(i, Right, 0);}
|
|
}
|
|
else if (block[i].style == 1) { //2*1
|
|
if ((Check_Empty(addr, Up, 1) == true) &&
|
|
(Check_Empty(addr + 1, Up, 1) == true)) {Move_Block(i, Up, 0);}
|
|
|
|
if ((Check_Empty(addr, Down, 1) == true) &&
|
|
(Check_Empty(addr + 1, Down, 1) == true)) {Move_Block(i, Down, 0);}
|
|
|
|
if (Check_Empty(addr, Left, 1) == true) {
|
|
Move_Block(i, Left, 0);
|
|
if (Check_Empty(addr, Left, 2) == true) {Move_Block(i, Left, Left);}
|
|
}
|
|
|
|
if (Check_Empty(addr, Right, 2) == true) {
|
|
Move_Block(i, Right, 0);
|
|
if (Check_Empty(addr, Right, 3) == true) {Move_Block(i, Right, Right);}
|
|
}
|
|
}
|
|
else if (block[i].style == 2) { //1*2
|
|
if (Check_Empty(addr, Up, 1) == true) {
|
|
Move_Block(i, Up, 0);
|
|
if (Check_Empty(addr, Up, 2) == true) {Move_Block(i, Up, Up);}
|
|
}
|
|
|
|
if (Check_Empty(addr, Down, 2) == true) {
|
|
Move_Block(i, Down, 0);
|
|
if (Check_Empty(addr, Down, 3) == true) {Move_Block(i, Down, Down);}
|
|
}
|
|
|
|
if ((Check_Empty(addr, Left, 1) == true) &&
|
|
(Check_Empty(addr + 4, Left, 1) == true)) {Move_Block(i, Left, 0);}
|
|
|
|
if ((Check_Empty(addr, Right, 1) == true) &&
|
|
(Check_Empty(addr + 4, Right, 1) == true)) {Move_Block(i, Right, 0);}
|
|
}
|
|
else if (block[i].style == 3) { //1*1
|
|
if (Check_Empty(addr, Up, 1) == true) {
|
|
Move_Block(i, Up, 0);
|
|
if (Check_Empty(addr - 4, Up, 1) == true) {Move_Block(i, Up, Up);}
|
|
if (Check_Empty(addr - 4, Left, 1) == true) {Move_Block(i, Up, Left);}
|
|
if (Check_Empty(addr - 4, Right, 1) == true) {Move_Block(i, Up, Right);}
|
|
}
|
|
|
|
if (Check_Empty(addr, Down, 1) == true) {
|
|
Move_Block(i, Down, 0);
|
|
if (Check_Empty(addr + 4, Down, 1) == true) {Move_Block(i, Down, Down);}
|
|
if (Check_Empty(addr + 4, Left, 1) == true) {Move_Block(i, Down, Left);}
|
|
if (Check_Empty(addr + 4, Right, 1) == true) {Move_Block(i, Down, Right);}
|
|
}
|
|
|
|
if (Check_Empty(addr, Left, 1) == true) {
|
|
Move_Block(i, Left, 0);
|
|
if (Check_Empty(addr - 1, Up, 1) == true) {Move_Block(i, Left, Up);}
|
|
if (Check_Empty(addr - 1, Down, 1) == true) {Move_Block(i, Left, Down);}
|
|
if (Check_Empty(addr - 1, Left, 1) == true) {Move_Block(i, Left, Left);}
|
|
}
|
|
|
|
if (Check_Empty(addr, Right, 1) == true) {
|
|
Move_Block(i, Right, 0);
|
|
if (Check_Empty(addr + 1, Up, 1) == true) {Move_Block(i, Right, Up);}
|
|
if (Check_Empty(addr + 1, Down, 1) == true) {Move_Block(i, Right, Down);}
|
|
if (Check_Empty(addr + 1, Right, 1) == true) {Move_Block(i, Right, Right);}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
bool Check_Empty (unsigned char address, unsigned char dir, unsigned char num) { //判断指定位置是否为空格 若不是空格或者无效返回false
|
|
unsigned char x, y, addr;
|
|
if (address > 19) {return false;} //输入位置不存在
|
|
|
|
x = address % 4;
|
|
y = (address - x) / 4;
|
|
if (dir == Up) { //上方
|
|
if (y < num) {return false;}
|
|
addr = address - num * 4;
|
|
}
|
|
if (dir == Down) { //下方
|
|
if (y + num > 4) {return false;}
|
|
addr = address + num * 4;
|
|
}
|
|
if (dir == Left) { //左侧
|
|
if (x < num) {return false;}
|
|
addr = address - num;
|
|
}
|
|
if (dir == Right) { //右侧
|
|
if(x + num > 3){return false;}
|
|
addr = address + num;
|
|
}
|
|
|
|
if (table[addr] == 0xA) {
|
|
return true;
|
|
} else {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
unsigned int Get_Code() { //生成编码
|
|
bool temp[20];
|
|
unsigned int Code = 0;
|
|
unsigned char i, addr, style;
|
|
|
|
for (i = 0; i < 20; i++) {temp[i] = false;} //初始化
|
|
temp[block[0].address] = temp[block[0].address + 1] =
|
|
temp[block[0].address + 4] = temp[block[0].address + 5] = true;
|
|
|
|
Code |= block[0].address<<24; //2*2块的位置
|
|
addr = 0;
|
|
for (i = 1; i <= 11; i++) {
|
|
while(temp[addr] == true){ //找到下一个未填充的空格
|
|
if (addr < 19) {
|
|
addr++;
|
|
} else {
|
|
return 0;
|
|
}
|
|
}
|
|
if (table[addr] == 0xA) { //空格
|
|
temp[addr] = true;
|
|
} else {
|
|
style = block[table[addr]].style;
|
|
if (style == 1) { //2*1
|
|
temp[addr] = temp[addr + 1] = true;
|
|
Code |= 1<<(24 - i * 2);
|
|
}
|
|
else if (style == 2) { //1*2
|
|
temp[addr] = temp[addr + 4] = true;
|
|
Code |= 2<<(24 - i * 2);
|
|
}
|
|
else if (style == 3) { //1*1
|
|
temp[addr] = true;
|
|
Code |= 3<<(24 - i * 2);
|
|
}
|
|
}
|
|
}
|
|
return Code;
|
|
}
|
|
|
|
void Analyse_Code (unsigned int Code) { //解译编码到 table[20] block[10] space[2]中
|
|
unsigned char i, addr, style;
|
|
unsigned char num_space = 0, num_type_1 = 0, num_type_2 = 5;
|
|
space[0] = space[1] = 0xFF; //初始化
|
|
for (i = 0; i < 20; i++) {table[i] = 0xFF;}
|
|
for (i = 0; i <= 9; i++) {
|
|
block[i].address = 0xFF;
|
|
block[i].style = 0xFF;
|
|
}
|
|
|
|
block[0].address = 0xF & (Code>>24); //开始解译
|
|
if (block[0].address > 14) {goto err;} //2*2块越界 退出
|
|
block[0].style = 0; //设置2*2块的参数
|
|
Fill_Block(block[0].address, 0, 0x0);
|
|
addr = 0;
|
|
for (i = 0; i < 11; i++) { //遍历 10个块
|
|
while (table[addr] != 0xFF){ //向下搜索空块
|
|
if (addr < 19) {
|
|
addr++;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
style = 0x3 & (Code>>(22 - i * 2)); //0:space 1:2*1 2:1*2 3:1*1
|
|
if (style == 0) { //space
|
|
table[addr] = 0xA;
|
|
space[num_space] = addr;
|
|
if (num_space == 0) {num_space++;}
|
|
}
|
|
if (style == 1) { //2*1
|
|
if (num_type_1 < 5) {num_type_1++;}
|
|
if (addr > 18) {goto err;} //2*1块越界
|
|
block[num_type_1].style = 1;
|
|
block[num_type_1].address = addr;
|
|
table[addr] = table[addr + 1] = num_type_1;
|
|
}
|
|
if (style == 2) { //1*2
|
|
if (num_type_1 < 5) {num_type_1++;}
|
|
if (addr > 15) {goto err;} //1*2块越界
|
|
block[num_type_1].style = 2;
|
|
block[num_type_1].address = addr;
|
|
table[addr] = table[addr + 4] = num_type_1;
|
|
}
|
|
if (style == 3) { //1*1
|
|
if (num_type_2 < 9) {num_type_2++;}
|
|
block[num_type_2].style = 3;
|
|
block[num_type_2].address = addr;
|
|
table[addr] = num_type_2;
|
|
}
|
|
}
|
|
err:;
|
|
}
|
|
|
|
bool Check (unsigned int Code) { //检查编码是否合法 正确返回true 错误返回false
|
|
bool temp[20];
|
|
unsigned char addr, i;
|
|
Analyse_Code(Code);
|
|
|
|
for (i = 0; i < 20; i++){temp[i] = false;} //初始化
|
|
for (i = 0; i < 20; i++) { //检查table内容是否合法
|
|
if (table[i] > 10) {return false;}
|
|
}
|
|
|
|
if (block[0].style != 0) {return false;} //检查2*2块
|
|
for (i = 1; i <= 5; i++) { //检查2*1与1*2块
|
|
if ((block[i].style != 1) && (block[i].style != 2)) {return false;}
|
|
}
|
|
for (i = 6; i <= 9; i++) { //检查1*1块
|
|
if (block[i].style != 3) {return false;}
|
|
}
|
|
for (i = 0; i <= 1; i++) { //检查空格
|
|
if (space[i] > 19) {
|
|
return false;
|
|
} else {
|
|
temp[space[i]] = true;
|
|
}
|
|
}
|
|
|
|
addr = block[0].address; //检查2*2块
|
|
if ((addr > 14) || (addr%4 == 3)) {return false;}
|
|
if ((temp[addr] == true) || (temp[addr + 1] == true) ||
|
|
(temp[addr + 4] == true) || (temp[addr + 5] == true)) {return false;}
|
|
temp[addr] = temp[addr + 1] = temp[addr + 4] = temp[addr + 5] = true;
|
|
for (i = 1; i <= 5; i++) { //检查2*1与1*2块
|
|
addr = block[i].address;
|
|
if (block[i].style == 1) {
|
|
if ((addr > 18) || (addr % 4 == 3)) {return false;}
|
|
if ((temp[addr] == true) || (temp[addr + 1] == true)) {return false;}
|
|
temp[addr] = temp[addr + 1] = true;
|
|
}
|
|
if (block[i].style == 2) {
|
|
if (addr > 15) {return false;}
|
|
if ((temp[addr] == true) || (temp[addr + 4] == true)) {return false;}
|
|
temp[addr] = temp[addr + 4] = true;
|
|
}
|
|
}
|
|
for (i = 6; i <= 9; i++) { //检查1*1块
|
|
addr = block[i].address;
|
|
if (addr > 19) {return false;}
|
|
if (temp[addr] == true) {return false;}
|
|
temp[addr] = true;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
string Change_str (unsigned int dat) { //将编码数据转化为字符
|
|
unsigned char i, bit;
|
|
string str = "";
|
|
for (i = 0; i < 7; i++) {
|
|
bit = 0xF & dat>>(6 - i)*4; //分离单个十六进制位
|
|
if ((bit >= 0) && (bit <= 9)) {str += bit + 48;} //0~9
|
|
if ((bit >= 0xA) && (bit <= 0xF)) {str += bit + 55;} //A~F
|
|
}
|
|
return str;
|
|
}
|
|
|
|
unsigned int Change_int (char str[8]) { //将编码字符转化为int
|
|
unsigned int i, dat = 0;
|
|
for (i = 0; i < 7; i++) {
|
|
if ((str[i] >= 48) && (str[i] <= 57)) {dat = dat | (str[i] - 48)<<(24 - i * 4);} //0~9
|
|
if ((str[i] >= 65) && (str[i] <= 70)) {dat = dat | (str[i] - 55)<<(24 - i * 4);} //A~F
|
|
if ((str[i] >= 97) && (str[i] <= 102)) {dat = dat | (str[i] - 87)<<(24 - i * 4);} //a~f
|
|
}
|
|
return dat;
|
|
}
|
|
|
|
void Find_All_Case(){ //Right_File's MD5: 4A0179C6AEF266699A73E41ECB4D87C1
|
|
File_Output.open("All_Case.txt");
|
|
unsigned int i;
|
|
for (i = 0; i < 0xFFFFFFF; i += 4) {
|
|
if (Check(i) == true) {File_Output << Change_str(i) << endl;}
|
|
}
|
|
File_Output.close();
|
|
}
|
|
|
|
void Data_Output(string File_name){
|
|
unsigned int i, j, layer;
|
|
File_Output.open(File_name.c_str());
|
|
File_Output << "[Group_size]" << endl << group_size << endl;
|
|
File_Output << "[Min_steps]" << endl << min_steps << endl;
|
|
File_Output << "[Farthest_steps]" << endl << farthest_steps << endl;
|
|
File_Output << "[Min_Solutions]" << endl;
|
|
for (i = 0; i < min_Solutions.size(); i++) {
|
|
File_Output << Change_str(min_Solutions[i]) << endl;
|
|
}
|
|
File_Output << "[Farthest_cases]" << endl;
|
|
for (i = 0; i < farthest_cases.size(); i++) {
|
|
File_Output << Change_str(farthest_cases[i]) << endl;
|
|
}
|
|
File_Output << "[Solutions]" << endl;
|
|
for (i = 0; i < Solutions.size(); i++) {
|
|
File_Output << Change_str(Solutions[i]) << " (" << Solutions_steps[i] << ")" << endl;
|
|
}
|
|
File_Output << "[List]" << endl;
|
|
for (i = 0; i < List.size(); i++) {
|
|
File_Output << i << " -> " << Change_str(List[i]) << " (" << Layer_Num[i] << "," << Layer_Index[i] << ")" << endl;
|
|
}
|
|
File_Output << "[Layer]" << endl;
|
|
for (layer = 0; layer < Layer.size(); layer++) {
|
|
for (i = 0; i < Layer_Next[layer].size(); i++) {
|
|
File_Output << "(" << layer << "," << i << ")" << " -> ";
|
|
for (j = 0; j < Layer_Next[layer][i].size(); j++) {
|
|
File_Output << "(" << (layer+1) << "," << Layer_Next[layer][i][j] << ") ";
|
|
}
|
|
File_Output << endl;
|
|
}
|
|
}
|
|
File_Output.close();
|
|
}
|
|
|