huidong

高二数学建模的代码备份

这个是我在学校写了一个周末的代码（暴力穷举，效果极差，，，浪费一个周末）

#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;
}