种菜建模代码备份
[編輯] [转简体] （简体译文）
|
作者：huidong
| 分類：【算法】種菜算法
[
24 瀏覽
0 評論
7 贊
8 踩
]
概要
正文
高二数学建模的代码备份
这个是我在学校写了一个周末的代码（暴力穷举，效果极差，，，浪费一个周末）
#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;
}