种菜建模代码备份
[編輯] [转简体] (简体译文)
|
作者:huidong
| 分類:【算法】種菜算法
[
10 瀏覽
0 評論
2 贊
2 踩
]
概要
正文
高二数学建模的代码备份
这个是我在学校写了一个周末的代码(暴力穷举,效果极差,,,浪费一个周末)
#include <stdio.h> #include <time.h> #include <graphics.h> #include <algorithm> #include <vector> using namespace std; // 实际问题参数 struct Problem { int w, h; int door_len; int door_pos; int block_x, block_y; int block_len; int pavement_width; vector<SIZE> vec_pot_types; }; struct Pot; // 盆边路 struct PotRoad { vector<POINT> vec_pts; // 此路所占点集 vector<Pot*> vec_occupier; // 占路的盆集 }; // 盆的全部(包括路) class Pot { public: int type; // 盆的类型 vector<POINT> vec_pot_pts; // 盆身所占点集 vector<PotRoad> vec_roads; // 盆的路集 vector<PotRoad*> vec_occupy_roads; // 盆身所侵占别人的路集 // 是否还存在未被侵占的道路 bool IsUnoccupiedRoad() { for (auto& element : vec_roads) { if (!element.vec_occupier.size()) { return true; } } return false; } }; // 最小地皮单元 struct Land { bool flag_pot = false; // 盆身 bool flag_road = false; // 盆路 bool flag_entry = false; // 入口区 bool flag_block = false; // 障碍区 bool flag_reachable = false; // 可否到达 // 存储该地所属盆路或盆身 // 若该地属于盆身,则 PotRoad 为空 // 若该地属于盆路,则 Pot 和 PotRoad 都非空 vector<pair<Pot*, PotRoad*>> vec_pots_pair; }; // 记录一个操作 struct Operation { POINT pt; Pot* pot = nullptr; // 记录放置的盆(为空表示此操作留空此地) }; // 存储解决方案 struct Solution { Land** area; // 地图 vector<Pot*> vec_pots; // 盆集(此处存储的盆都是分配在内存中的) vector<Operation> vec_op; // 操作记录 }; ///////////////// functions ///////////////////// // 确认道路覆盖(如果可以覆盖,将记录覆盖情况) // pot_covered 被挡住路的盆 // road_covered 被挡住的路 // pot_covered 挡别人路的盆 // 返回是否允许覆盖 bool CheckAndRecordOverlay(Pot* pot_covered, PotRoad* road_covered, Pot* pot_cover) { bool flag = false; // 标记是否允许占用 // 若此路本就被别人覆盖,则再占此路也可以 if (road_covered->vec_occupier.size() > 0) { road_covered->vec_occupier.push_back(pot_cover); flag = true; } else { // 尝试侵占,看侵占后还有没有可用道路剩余 road_covered->vec_occupier.push_back(pot_cover); if (pot_covered->IsUnoccupiedRoad()) // 可以侵占 { flag = true; } else // 不可侵占 { road_covered->vec_occupier.pop_back(); } } // 记录侵占的路 if (flag) { pot_cover->vec_occupy_roads.push_back(road_covered); } return flag; } // 将填充矩形的点(盆身或盆路)加入到盆的某一容器中(若加入的矩形超出边界,则不加入) // pt 加入矩形的左上角位置 // size 矩形大小 // border 边界大小 // pot 盆自身 // road 如果是路,传入路的指针 // vec_dst 目标容器 // vec_pots_affected 创建盆路时,用于返回受到影响的盆 // is_pot_body 是否为盆身 // 返回值:是否加入成功 bool AddRectPtsToVector( Problem *problem, Solution* solution, POINT pt, SIZE size, SIZE border, Pot& pot, PotRoad* p_road, vector<POINT>& vec_dst, bool is_pot_body ) { if (pt.x >= 0 && pt.y >= 0 && pt.x + size.cx <= border.cx && pt.y + size.cy <= border.cy) { vector<POINT> temp; // 临时存储,如果遇到障碍则放弃 // 将矩形的每个点都放入容器 for (int x = pt.x; x < pt.x + size.cx; x++) { for (int y = pt.y; y < pt.y + size.cy; y++) { // 当前点 Land& land = solution->area[x][y]; // 确认该点可否覆盖 if( ( is_pot_body // 盆身不覆盖他人盆身、入口和障碍 && !land.flag_pot && !land.flag_entry && !land.flag_block ) || (!is_pot_body // 盆路不覆盖障碍 && !land.flag_block ) ) { if (is_pot_body && land.flag_road) // 盆身压到他人盆路 { // 看是谁的路(可能是好几个盆的路 for (auto& element : land.vec_pots_pair) { // 如果之前没压过,就问问他 if (element.second && !count( pot.vec_occupy_roads.begin(), pot.vec_occupy_roads.end(), element.second)) { // 询问 if (!CheckAndRecordOverlay(element.first, element.second, &pot)) { return false; // 不能压,算了吧 } } } } if (!is_pot_body && land.flag_pot) // 他人盆身可能覆盖此盆路 { // 由于此地是他人盆身,所以这里只需要找出一个盆身 Pot* pot_cover = nullptr; for (auto& pot_pair : land.vec_pots_pair) { // 发现盆身 if (!pot_pair.second) { pot_cover = pot_pair.first; } } // 若该盆身对我的路的阻挡已经记录,则无需再重复 if (!count( p_road->vec_occupier.begin(), p_road->vec_occupier.end(), pot_cover)) { // 直接手动登记,全部道路创建完毕后再看是否存在可用道路 pot_cover->vec_occupy_roads.push_back(p_road); p_road->vec_occupier.push_back(pot_cover); } } temp.push_back({x, y}); } else // 如果有任意一点不符合要求,则此点集作废 { return false; } } } //// 合并临时容器 //set_union(vec_dst.begin(), vec_dst.end(), temp.begin(), temp.end(), vec_dst.begin()); vec_dst = temp; return true; } else { return false; } } // 删除盆 void DeletePot(Problem *problem, Solution* solution, Pot* pot) { // 遍历我占用的路,让他们知道我不占用他们了 for (auto& road : pot->vec_occupy_roads) { for (size_t i = 0; i < road->vec_occupier.size(); i++) { if (road->vec_occupier[i] == pot) { road->vec_occupier.erase(road->vec_occupier.begin() + i); } } } // 遍历占用我路的盆,让他们知道他们不再占用我的路了 for (auto& road : pot->vec_roads) { for (auto& occupier : road.vec_occupier) { for (size_t i = 0; i < occupier->vec_occupy_roads.size(); i++) { if (occupier->vec_occupy_roads[i] == &road) { occupier->vec_occupy_roads.erase(occupier->vec_occupy_roads.begin() + i); } } } } // 在地图上删去标记 // 删除盆身标记 for (auto& pt : pot->vec_pot_pts) { solution->area[pt.x][pt.y].flag_pot = false; auto& vec_pots_pair = solution->area[pt.x][pt.y].vec_pots_pair; for (size_t i = 0; i < vec_pots_pair.size(); i++) { if (vec_pots_pair[i].first == pot) { vec_pots_pair.erase(vec_pots_pair.begin() + i); } } } // 删除盆路标记 for (auto& road : pot->vec_roads) { for (auto& pt : road.vec_pts) { auto& vec_pots_pair = solution->area[pt.x][pt.y].vec_pots_pair; for (size_t i = 0; i < vec_pots_pair.size(); i++) { if (vec_pots_pair[i].second == &road) { vec_pots_pair.erase(vec_pots_pair.begin() + i); } } // 删去我的盆路后,这个点上还是否存在其它盆路 bool is_any_road = false; for (auto& pot_pair : vec_pots_pair) { if (pot_pair.second) { is_any_road = true; break; } } // 如果该点不存在任何道路了,就标记其道路属性为 false if (!is_any_road) { solution->area[pt.x][pt.y].flag_road = false; } } } // 删除盆登记 for (size_t i = 0; i < solution->vec_pots.size(); i++) { if (solution->vec_pots[i] == pot) { solution->vec_pots.erase(solution->vec_pots.begin() + i); } } // 清空内存 delete pot; } // 创建一个盆 // pot 传出创建的盆 // 返回是否创建成功 bool CreatePot(Problem *problem, Solution* solution, POINT pt, int type, Pot *pot) { // 地图边界 SIZE border = {problem->w, problem->h}; // 盆身大小 int w = problem->vec_pot_types[type].cx; int h = problem->vec_pot_types[type].cy; // 盆类型 pot->type = type; // 创建盆身 if (!AddRectPtsToVector( problem, solution, pt, {w, h}, border, *pot, nullptr, pot->vec_pot_pts, true )) { return false; } // 向上、下扩展道路 if (w >= h) { POINT pt_up = {pt.x, pt.y - problem->pavement_width}; // 道路左上角 POINT pt_down = {pt.x, pt.y + h}; SIZE pavement = {w, problem->pavement_width}; // 道路矩形大小 PotRoad road_up, road_down; // 如果道路创建成功,则加入到盆中 if (AddRectPtsToVector( problem, solution, pt_up, pavement, border, *pot, &road_up, road_up.vec_pts, false )) { pot->vec_roads.push_back(road_up); } if (AddRectPtsToVector( problem, solution, pt_down, pavement, border, *pot, &road_down, road_down.vec_pts, false )) { pot->vec_roads.push_back(road_down); } } // 向左、右扩展道路 if (w <= h) { POINT pt_left = {pt.x - problem->pavement_width, pt.y}; POINT pt_right = {pt.x + w, pt.y}; SIZE pavement = {problem->pavement_width, h}; PotRoad road_left, road_right; if (AddRectPtsToVector( problem, solution, pt_left, pavement, border, *pot, &road_left, road_left.vec_pts, false )) { pot->vec_roads.push_back(road_left); } if (AddRectPtsToVector( problem, solution, pt_right, pavement, border, *pot, &road_right, road_right.vec_pts, false )) { pot->vec_roads.push_back(road_right); } } // 若没有可用道路,则需要删除这个盆 if (!pot->IsUnoccupiedRoad()) { DeletePot(problem, solution, pot); return false; } else { Operation op; op.pot = pot; op.pt = pt; solution->vec_pots.push_back(pot); // 记录创建的盆 solution->vec_op.push_back(op); // 记录操作 // 在地图上登记 for (auto& _pt : pot->vec_pot_pts) { Land& land = solution->area[_pt.x][_pt.y]; land.flag_pot = true; land.vec_pots_pair.push_back(make_pair(pot, nullptr)); } for (auto& road : pot->vec_roads) { for (auto& _pt : road.vec_pts) { Land& land = solution->area[_pt.x][_pt.y]; land.flag_road = true; land.vec_pots_pair.push_back(make_pair(pot, &road)); } } return true; } } // 获取下一个操作点 // pt 当前位置 // pOut 返回下一个操作位置 // 返回值:是否找到下一个操作点 bool FindNextOpPoint(Problem *problem, Solution* solution, POINT pt, POINT *pOut) { int x = pt.x + 1; for (int y = pt.y; y< problem->h; y++) { for (; x < problem->w ; x++) // 向右、下寻找,所以 x 先加一 { Land land = solution->area[x][y]; if ( !land.flag_pot && !land.flag_entry && !land.flag_block ) { *pOut = {x, y}; return true; } } x = 0; } return false; } // 耶耶耶!yep // 终于可以展示方案了么?! void ShowSolution(Problem *problem, Solution* solution) { int w = problem->w; int h = problem->h; int len = 10; initgraph(w * len, h * len); for (auto& pot : solution->vec_pots) { int type = pot->type; SIZE size = problem->vec_pot_types[type]; POINT pt = pot->vec_pot_pts[0]; setfillcolor(YELLOW); fillrect(pt.x * len, pt.y * len, (pt.x + size.cx) * len, (pt.y + size.cy) * len); } for (int x = 0; x < w; x++) { for (int y = 0; y < h; y++) { Land& land = solution->area[x][y]; COLORREF color = WHITE; if (land.flag_pot) { //color = YELLOW; continue; } if (land.flag_road) { //continue; color = GREEN; } if (land.flag_entry) { color = BLUE; } if (land.flag_block) { color = BLACK; } setfillcolor(color); fillrect(x * len, y * len, (x + 1) * len, (y + 1) * len); //putpixel(x, y, color); } } getch(); closegraph(); } // 获取解决方案 void GetSolution(Problem *problem, Solution* solution) { POINT pt_now = { 0, 0 }; // 当前操作点 int type_suggest = 0; // 回溯时,建议的盆类型 int types_sum = problem->vec_pot_types.size(); // 盆类总数 int solution_sum = 0; while (true) { //if (type_suggest == 0) // type_suggest = rand() % 20; int type = type_suggest; // 尝试在当前点创建菜盆 while (true) { Pot *p_pot = new Pot; // 如果类型已经试尽,则标记此地为空 if (type >= types_sum) { Operation op; op.pot = nullptr; op.pt = pt_now; solution->vec_op.push_back(op); break; } // 如果盆创建成功,则退出尝试 if (CreatePot(problem, solution, pt_now, type, p_pot)) { break; } else { delete p_pot; } type++; } // 如果有建议的盆类型,应该在创建盆后将其置零 if (type_suggest != 0) { type_suggest = 0; } // 尝试寻找下一个操作点 if (!FindNextOpPoint(problem, solution, pt_now, &pt_now)) { // 未找到下一个操作点,说明已经完成一种方案 solution_sum++; //if (solution_sum == 22222000) ShowSolution(problem, solution); // 测试方案 while (solution->vec_op.size()) { // 进行回溯,看看最后一个加入的是什么 Operation last_op = *(solution->vec_op.end() - 1); solution->vec_op.pop_back(); // 如果最后一个加入的是盆,那么删除这个盆,并建议接下来尝试下一种类型的盆 if (last_op.pot) { type_suggest = last_op.pot->type + 1; pt_now = last_op.pt; DeletePot(problem, solution, last_op.pot); break; } // 如果最后的一次操作留空,说明这个点的盆类已经试尽了,需要再往上回溯 else { // 如果已经回溯到尽头,说明已经穷举完所有方案了 if (!solution->vec_op.size()) { getch(); //return ; } } } } } } // 读入问题参数 bool ReadProblem(Problem *p) { FILE *fp = fopen("./data.txt", "r"); if (fp) { char szFormat[] = "%d %d\n" // w h "%d %d\n" // door_len door_pos "%d %d %d\n" // block_x y len "%d\n"; // pavement_width if (!fscanf( fp, szFormat, &p->w, &p->h, &p->door_len, &p->door_pos, &p->block_x, &p->block_y, &p->block_len, &p->pavement_width )) { fclose(fp); return false; } int pot_w = 0, pot_h = 0; while (fscanf(fp, "%d %d\n", &pot_w, &pot_h) != -1) { p->vec_pot_types.push_back({pot_w, pot_h}); } fclose(fp); return true; } else { return false; } } // 将已有的不重复盆类型集全部旋转并加入原集(不旋转正方形) void RotatePotTypes(vector<SIZE>& types) { for (auto& child : types) { if (child.cx != child.cy) { types.push_back({child.cy, child.cx}); } } } // 初始化解决方案 void InitSolution(Problem *problem, Solution *solution) { solution->area = new Land*[problem->w]; for (int i = 0; i < problem->w; i++) { solution->area[i] = new Land[problem->h]; } } // 删除解决方案 void DeleteSolution(Problem *problem, Solution *solution) { for (int i = 0; i < problem->w; i++) { delete[] solution->area[i]; } delete[] solution->area; for (auto& pot : solution->vec_pots) { delete pot; } } // 载入问题到解决方案 void LoadProblemToSolution(Problem* problem, Solution* solution) { // 标记门的位置 int door_w = problem->pavement_width; int door_h = problem->door_len; int door_y = problem->door_pos; for (int y = door_y; y < door_y + door_h && y < problem->h; y++) { for (int x = 0; x < door_w && x < problem->w; x++) { solution->area[x][y].flag_entry = true; } } // 标记障碍物的位置 int block_x = problem->block_x; int block_y = problem->block_y; int block_len = problem->block_len; for (int y = block_y; y < block_y + block_len && y < problem->h; y++) { for (int x = block_x; x < block_x + block_len && x < problem->w; x++) { solution->area[x][y].flag_block = true; } } } int main() { Problem problem; Solution solution; srand((UINT)time(0)); // 读入问题 if (!ReadProblem(&problem)) { printf("Data file not found!\n"); return -1; } // 得到旋转后的盆 RotatePotTypes(problem.vec_pot_types); for (auto& type : problem.vec_pot_types) printf("%ld x %ld\n", type.cx, type.cy); //printf("%lld\n", problem.vec_pot_types.size()); // 新建解决方案 InitSolution(&problem, &solution); // 载入问题到解决方案 LoadProblemToSolution(&problem, &solution); // 获取解决方案 GetSolution(&problem, &solution); // 删除解决方案 DeleteSolution(&problem, &solution); printf("ok"); return 0; }