抱歉,您需设置社区昵称后才能参与社区互动!
2020软件开发创新大赛
话题 : 8 成员 : 197
1)user0060
2)
华为云账号:user0150
作业完成
杨宇--作业.rar 13.14 MB,下载次数:1
2020-12-1 09:31 上传
点击文件名下载附件
#include <iostream>
#include <fstream>
#include<vector>
#include <queue>
#include <stack>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
int maskMap[12][12] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
int minstep = 500;
struct Node
{
int x, y, mount;
char name;
Node(int x, int y, int m, char name) { this->x = x, this->y = y, mount = m; this->name = name; }
Node() { x = y = mount = name = 0; };
bool inBox(Node& l, Node& r);
int getDistance(Node& r)const;
bool operator == (Node& r) {
return (x == r.x) && (y == r.y);
}
int Node::getDistance(Node& r) const
return abs(x - r.x) + abs(y - r.y);
bool Node::inBox(Node& l, Node& r)
return (((l.x <= x) && (x <= r.x)) or (((l.x >= x) && (x >= r.x))))
&& (((l.y <= y) && (y <= r.y)) or ((l.y >= y) && (y >= r.y)));
struct status
char path[40];
char walkPath[500];
int crt_step;
int map[12][12];
status() { path[0] = 'S'; step = 0; crt_step = 0; depth = 1; next = 0; walkPath[0] = 0; }
Node courier;
vector<Node> v_demand, v_denote;
int step;
int depth;
int next;//深度优先回溯下标
void get(int index);
int getOnePath();//获得可行解
void give(int index);
status getNext();
bool haveNext();
void addNode(Node node);
void output();
void outputPath();
void outputBest();
int getMaxRatio();
void iniMap();
void walk();
void walk(char dir);
char* getWay(char A, char B, char* way)const;
char* getWay(Node A, Node B, char* way)const;
void getWalkPath();
void go(char name);
Node GetNodeFromName(char name) const;
bool finish();
void cleanBoard();
void status::iniMap()
for (int i = 0; i < 12; i++)
for (int j = 0; j < 12; j++)
map[i][j] = maskMap[i][j] = 0;
for (int i = 0; i < v_demand.size(); i++)
Node& node = v_demand[i];
maskMap[node.x][node.y] = node.mount;
for (int i = 0; i < v_denote.size(); i++)
Node& node = v_denote[i];
map[i][j] = maskMap[i][j];
bool status::finish()
cleanBoard();
return walkPath[crt_step] == 0;
void status::walk(char dir)
switch (dir)
case 'W': courier.y--; break;
case 'N': courier.x--; break;
case 'S': courier.x++; break;
case 'E': courier.y++; break;
if (courier.x < 0 || courier.x > 11 || courier.y < 0 || courier.y > 11)
cout << "out of space!" << endl;
int s;
cin >> s;
if (map[courier.x][courier.y] + courier.mount > 0)
courier.mount += map[courier.x][courier.y];
if (courier.mount > 100) courier.mount = 100;
map[courier.x][courier.y] = 0;
else
map[courier.x][courier.y] += courier.mount;
courier.mount = 0;
map[v_denote[0].x][v_denote[0].y] = 5000;
Node status::GetNodeFromName(char name) const
switch (name)
case 'A':
case 'B':
case 'C':
case 'D':
case 'E':
if (v_demand[i].name == name) return v_demand[i];
break;
default:
if (v_denote[i].name == name) return v_denote[i];
return v_denote[0];
char* status::getWay(Node from, Node to, char* way) const
int x, y;
int i, j;
x = to.x - from.x;
y = to.y - from.y;
for (i = 0; i < abs(x); i++)
if (x < 0)way[i] = 'N';
else way[i] = 'S';
for (j = 0; j < abs(y); j++)
if (y < 0) way[i + j] = 'W';
else way[i + j] = 'E';
way[i + j] = 0;
return way;
char* status::getWay(char A, char B, char* way)const
Node from, to, tmp;
tmp = from = GetNodeFromName(A);
to = GetNodeFromName(B);
return getWay(from, to, way);
void status::walk()
if (walkPath[crt_step] == 0) return;
cout << walkPath[crt_step] << endl;
walk(walkPath[crt_step]);
crt_step++;
void status::getWalkPath()
int i;
walkPath[0] = 0;
char way[40];
//cout << path << endl;
int len = strlen(path);
for (i = 0; i < len - 1; i++)
//
strcat(walkPath, getWay(path[i], path[i + 1], way));
//strcat(walkPath, getWay(path[i], path[i + 1], way));
//out<<path[i]<<"---"<<path[i+1]<<"\t" << way << endl;
vector<status> v_best;
float weight = 0;
int rltcnt = 0;
int status::getMaxRatio()
float maxRatio = 0, ratio;
int maxindex = 0, i;
for (i = 0; i < v_demand.size(); i++)
Node node = v_demand[i];
int give = -node.mount;
if (give > 100)give = 100;
if (give > courier.mount) give = courier.mount;
ratio = give / (float)courier.getDistance(v_demand[i]);
if (ratio > maxRatio)
maxRatio = ratio;
maxindex = i;
give = 100;
if (give > -node.mount) give = -node.mount;
ratio = give / (float)(v_denote[0].getDistance(v_demand[i]) + courier.getDistance(v_denote[0]));//回原点再去送
maxindex = -1;
if (node.inBox(courier, v_denote[0]))//在回原点路上
return i;
return maxindex;
int status::getOnePath()
int sum = 0;
sum += v_demand[i].mount;
while (v_demand.size() > 0)
int next = getMaxRatio();
if (next == -1)
get(0);
give(next);
if (v_demand.size() == 0)
return step;
if (courier.mount == 0)
void status::outputPath()
path[depth] = 0;
int i = 0;//out << path<<"\t";
int cnt[10] = { 0,0,0,0,0,0,0,0,0 };
for (i = 0; i < depth; i++)
if (path[i] != 'S')
//out << path[i];
cnt[path[i] - 'A'] ++;
//out << "\t*\t";
for (i = 0; i < 5; i++)
//out <<char( 'A' + i) << cnt[i];
//out << endl;
void status::addNode(Node node)
if (node.mount > 0)
v_denote.push_back(node);
else v_demand.push_back(node);
void status::outputBest()
//out<<depth << "\t" << step << "\t" ;
outputPath();
void status::output()
//out << int(courier.x) << "\t" << int(courier.y) << "\t" << courier.mount << endl;
for (i = 0; i < 12; i++)
for (j = 0; j < 12; j++) //
if (i == courier.x && j == courier.y && map[i][j] == 0)
}//out << courier.mount << "*";{}
}//out << map[i][j] << "\t";// = maskMap[i][j];
bool status::haveNext()
if (v_demand.size() == 0) return false;
if (step >= minstep) return false;
if (step + v_demand[0].getDistance(courier) > minstep) return false;
if (courier.mount == 100)
if (next < v_demand.size()) return true;
else if (courier.mount == 0)
if (next < v_denote.size())return true;
if (next < v_demand.size() + v_denote.size())return true;
return false;
int sltmod = 0;
status status::getNext()
status s;
s = *this;
if (courier.mount == 100)//满载
s.give(next);
next++;
return s;
else if (courier.mount == 0)//空载
s.get(next);
if (next < v_demand.size())//去配送小区
if (v_denote[0].inBox(courier, v_demand[next]))//去该小区经过仓库
s.v_demand.clear();
if (s.courier.mount + v_demand[next].mount < -100)//某个节点要去三次,剪枝。效率提高明显,通过实验,会错过部分最优解,但是能得到最优解,感觉在数学上两种情况是等价的,没证明
else//去取口罩
int denote;
denote = next - v_demand.size();
s.get(denote);
void status::go(char name)
if (name == v_demand[i].name)
give(i);
for (i = 0; i < v_denote.size(); i++)
if (name == v_denote[i].name)
get(i);
void status::get(int index)
Node& node = v_denote[index];
path[depth] = node.name;
depth++;
next = 0;
step += abs(courier.x - node.x) + abs(courier.y - node.y);
courier.x = node.x;
courier.y = node.y;
if (node.mount + courier.mount > 100)
node.mount -= (100 - courier.mount);
courier.mount = 100;
courier.mount += node.mount;
v_denote.erase(v_denote.begin() + index);
void status::give(int index)
Node& node = v_demand[index];
if (courier.mount + node.mount >= 0)
v_demand.erase(v_demand.begin() + index);
node.mount += courier.mount;
rltcnt++;
if (step <= minstep)
if (step < minstep) v_best.clear();
minstep = step;
v_best.push_back(*this);
void getBest(status s);
void status::cleanBoard()
if (walkPath[crt_step] != 0)
return;
int i, j, cnt = 0, mount = 0;
for (j = 0; j < 12; j++)
if (map[i][j] < 0)
s.addNode(Node(i, j, map[i][j], 'A' + cnt));
cnt++;
mount += map[i][j];
if (cnt == 0) return;
char way[30];
crt_step = 0;
Node c = courier;
if (mount + courier.mount > 0)
for (i = 0; i < s.v_demand.size(); i++)
strcat(walkPath, getWay(c, s.v_demand[i], way));
c = s.v_demand[i];
strcat(walkPath, getWay(c, v_denote[0], way));
strcat(walkPath, getWay(v_denote[0], s.v_demand[i], way));
//out << "in*******" << endl;
// output();
//cout<<"in ***** " << walkPath << endl;
int main()
minstep = 500;
rltcnt = 0;
char code;
status s, start;
int i = 0;
// cout << "----" << endl;
while (cin >> code)
switch (code)
case 'S':
cin >> x >> y;
// out << "S\t" << x << "\t" << y << endl;
s.courier = Node(x, y, 100, 'C');
s.addNode(Node(x, y, 5000, 'S'));
case 'R':
cin >> x >> y >> mount;
// out << "R\t" << x << "\t" << y << "\t" << mount << endl;
s.addNode(Node(x, y, mount, 'A' + i));
i++;
if (s.v_demand.size() == 5)
start = s;
start.getOnePath();
strcpy(s.path, start.path);
s.getWalkPath();
s.iniMap();
// s.output();
// out << s.path << endl;
// out << s.walkPath << endl;
case 'G':
s.walk();
if (s.finish())
goto lab;
lab:
return 0;
void getBest(status s)
stack<status> stk;
status start = s;
s.output();
minstep = s.getOnePath();
s.outputBest();
v_best.clear();
stk.push(start);
do {
status& top = stk.top();
status next;
if (top.haveNext())
next = top.getNext();
else stk.pop();
if (next.haveNext())
stk.push(next);
} while (!stk.empty());
//out << "best size\t" << v_best.size() << endl;
for (int i = 0; i < v_best.size(); i++)v_best[i].outputBest();
苏越鑫
角色:成员
话题:0
尼尼
Snice1993
user0150
冰山蓝魔
BuddhaLike
话题:1
游客
快速回复
您发表的内容存在敏感词汇
如点击继续发布,文章中的敏感词将正常发表。
1)user0060
2)
华为云账号:user0150
作业完成
2020-12-1 09:31 上传
点击文件名下载附件
#include <iostream>
#include <fstream>
#include<vector>
#include <queue>
#include <stack>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
int maskMap[12][12] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
int minstep = 500;
struct Node
{
int x, y, mount;
char name;
Node(int x, int y, int m, char name) { this->x = x, this->y = y, mount = m; this->name = name; }
Node() { x = y = mount = name = 0; };
bool inBox(Node& l, Node& r);
int getDistance(Node& r)const;
bool operator == (Node& r) {
return (x == r.x) && (y == r.y);
}
};
int Node::getDistance(Node& r) const
{
return abs(x - r.x) + abs(y - r.y);
}
bool Node::inBox(Node& l, Node& r)
{
return (((l.x <= x) && (x <= r.x)) or (((l.x >= x) && (x >= r.x))))
&& (((l.y <= y) && (y <= r.y)) or ((l.y >= y) && (y >= r.y)));
}
struct status
{
char path[40];
char walkPath[500];
int crt_step;
int map[12][12];
status() { path[0] = 'S'; step = 0; crt_step = 0; depth = 1; next = 0; walkPath[0] = 0; }
Node courier;
vector<Node> v_demand, v_denote;
int step;
int depth;
int next;//深度优先回溯下标
void get(int index);
int getOnePath();//获得可行解
void give(int index);
status getNext();
bool haveNext();
void addNode(Node node);
void output();
void outputPath();
void outputBest();
int getMaxRatio();
void iniMap();
void walk();
void walk(char dir);
char* getWay(char A, char B, char* way)const;
char* getWay(Node A, Node B, char* way)const;
void getWalkPath();
void go(char name);
Node GetNodeFromName(char name) const;
bool finish();
void cleanBoard();
};
void status::iniMap()
{
for (int i = 0; i < 12; i++)
{
for (int j = 0; j < 12; j++)
map[i][j] = maskMap[i][j] = 0;
}
for (int i = 0; i < v_demand.size(); i++)
{
Node& node = v_demand[i];
maskMap[node.x][node.y] = node.mount;
}
for (int i = 0; i < v_denote.size(); i++)
{
Node& node = v_denote[i];
maskMap[node.x][node.y] = node.mount;
}
for (int i = 0; i < 12; i++)
{
for (int j = 0; j < 12; j++)
map[i][j] = maskMap[i][j];
}
}
bool status::finish()
{
cleanBoard();
return walkPath[crt_step] == 0;
}
void status::walk(char dir)
{
switch (dir)
{
case 'W': courier.y--; break;
case 'N': courier.x--; break;
case 'S': courier.x++; break;
case 'E': courier.y++; break;
}
if (courier.x < 0 || courier.x > 11 || courier.y < 0 || courier.y > 11)
{
cout << "out of space!" << endl;
int s;
cin >> s;
}
if (map[courier.x][courier.y] + courier.mount > 0)
{
courier.mount += map[courier.x][courier.y];
if (courier.mount > 100) courier.mount = 100;
map[courier.x][courier.y] = 0;
}
else
{
map[courier.x][courier.y] += courier.mount;
courier.mount = 0;
}
map[v_denote[0].x][v_denote[0].y] = 5000;
}
Node status::GetNodeFromName(char name) const
{
switch (name)
{
case 'A':
case 'B':
case 'C':
case 'D':
case 'E':
for (int i = 0; i < v_demand.size(); i++)
{
if (v_demand[i].name == name) return v_demand[i];
}
break;
default:
for (int i = 0; i < v_denote.size(); i++)
{
if (v_denote[i].name == name) return v_denote[i];
}
break;
}
return v_denote[0];
}
char* status::getWay(Node from, Node to, char* way) const
{
int x, y;
int i, j;
x = to.x - from.x;
y = to.y - from.y;
for (i = 0; i < abs(x); i++)
if (x < 0)way[i] = 'N';
else way[i] = 'S';
for (j = 0; j < abs(y); j++)
if (y < 0) way[i + j] = 'W';
else way[i + j] = 'E';
way[i + j] = 0;
return way;
}
char* status::getWay(char A, char B, char* way)const
{
Node from, to, tmp;
tmp = from = GetNodeFromName(A);
to = GetNodeFromName(B);
return getWay(from, to, way);
}
void status::walk()
{
if (walkPath[crt_step] == 0) return;
cout << walkPath[crt_step] << endl;
walk(walkPath[crt_step]);
crt_step++;
}
void status::getWalkPath()
{
int i;
walkPath[0] = 0;
char way[40];
//cout << path << endl;
int len = strlen(path);
for (i = 0; i < len - 1; i++)
{
//
strcat(walkPath, getWay(path[i], path[i + 1], way));
//strcat(walkPath, getWay(path[i], path[i + 1], way));
//out<<path[i]<<"---"<<path[i+1]<<"\t" << way << endl;
}
}
vector<status> v_best;
float weight = 0;
int rltcnt = 0;
int status::getMaxRatio()
{
float maxRatio = 0, ratio;
int maxindex = 0, i;
for (i = 0; i < v_demand.size(); i++)
{
Node node = v_demand[i];
int give = -node.mount;
if (give > 100)give = 100;
if (give > courier.mount) give = courier.mount;
ratio = give / (float)courier.getDistance(v_demand[i]);
if (ratio > maxRatio)
{
maxRatio = ratio;
maxindex = i;
}
give = 100;
if (give > -node.mount) give = -node.mount;
ratio = give / (float)(v_denote[0].getDistance(v_demand[i]) + courier.getDistance(v_denote[0]));//回原点再去送
if (ratio > maxRatio)
{
maxRatio = ratio;
maxindex = -1;
}
if (node.inBox(courier, v_denote[0]))//在回原点路上
return i;
}
return maxindex;
}
int status::getOnePath()
{
int sum = 0;
int i;
for (i = 0; i < v_demand.size(); i++)
{
sum += v_demand[i].mount;
}
while (v_demand.size() > 0)
{
int next = getMaxRatio();
if (next == -1)
get(0);
else
{
give(next);
if (v_demand.size() == 0)
return step;
}
if (courier.mount == 0)
get(0);
}
return step;
}
void status::outputPath()
{
path[depth] = 0;
int i = 0;//out << path<<"\t";
int cnt[10] = { 0,0,0,0,0,0,0,0,0 };
for (i = 0; i < depth; i++)
{
if (path[i] != 'S')
{
//out << path[i];
cnt[path[i] - 'A'] ++;
}
}
//out << "\t*\t";
for (i = 0; i < 5; i++)
{
//out <<char( 'A' + i) << cnt[i];
}
//out << endl;
}
void status::addNode(Node node)
{
if (node.mount > 0)
v_denote.push_back(node);
else v_demand.push_back(node);
}
void status::outputBest()
{
//out<<depth << "\t" << step << "\t" ;
outputPath();
}
void status::output()
{
int i, j;
//out << int(courier.x) << "\t" << int(courier.y) << "\t" << courier.mount << endl;
for (i = 0; i < 12; i++)
{
for (j = 0; j < 12; j++) //
{
if (i == courier.x && j == courier.y && map[i][j] == 0)
{
}//out << courier.mount << "*";{}
else
{
}//out << map[i][j] << "\t";// = maskMap[i][j];
}
//out << endl;
}
//out << endl;
}
bool status::haveNext()
{
if (v_demand.size() == 0) return false;
if (step >= minstep) return false;
if (step + v_demand[0].getDistance(courier) > minstep) return false;
if (courier.mount == 100)
{
if (next < v_demand.size()) return true;
}
else if (courier.mount == 0)
{
if (next < v_denote.size())return true;
}
else
{
if (next < v_demand.size() + v_denote.size())return true;
}
return false;
}
int sltmod = 0;
status status::getNext()
{
status s;
s = *this;
if (courier.mount == 100)//满载
{
s.give(next);
next++;
return s;
}
else if (courier.mount == 0)//空载
{
s.get(next);
next++;
return s;
}
else
{
if (next < v_demand.size())//去配送小区
{
if (v_denote[0].inBox(courier, v_demand[next]))//去该小区经过仓库
{
s.v_demand.clear();
}
else
{
if (s.courier.mount + v_demand[next].mount < -100)//某个节点要去三次,剪枝。效率提高明显,通过实验,会错过部分最优解,但是能得到最优解,感觉在数学上两种情况是等价的,没证明
{
s.v_demand.clear();
next++;
return s;
}
s.give(next);
}
next++;
return s;
}
else//去取口罩
{
int denote;
denote = next - v_demand.size();
s.get(denote);
next++;
return s;
}
}
}
void status::go(char name)
{
int i;
for (i = 0; i < v_demand.size(); i++)
{
if (name == v_demand[i].name)
{
give(i);
}
}
for (i = 0; i < v_denote.size(); i++)
{
if (name == v_denote[i].name)
{
get(i);
}
}
}
void status::get(int index)
{
Node& node = v_denote[index];
path[depth] = node.name;
depth++;
path[depth] = 0;
next = 0;
step += abs(courier.x - node.x) + abs(courier.y - node.y);
courier.x = node.x;
courier.y = node.y;
if (node.mount + courier.mount > 100)
{
node.mount -= (100 - courier.mount);
courier.mount = 100;
}
else
{
courier.mount += node.mount;
v_denote.erase(v_denote.begin() + index);
}
}
void status::give(int index)
{
Node& node = v_demand[index];
step += abs(courier.x - node.x) + abs(courier.y - node.y);
path[depth] = node.name;
depth++;
path[depth] = 0;
next = 0;
courier.x = node.x;
courier.y = node.y;
if (courier.mount + node.mount >= 0)
{
courier.mount += node.mount;
v_demand.erase(v_demand.begin() + index);
}
else
{
node.mount += courier.mount;
courier.mount = 0;
}
if (v_demand.size() == 0)
{
rltcnt++;
if (step <= minstep)
{
if (step < minstep) v_best.clear();
minstep = step;
v_best.push_back(*this);
}
}
}
void getBest(status s);
void status::cleanBoard()
{
if (walkPath[crt_step] != 0)
return;
int i, j, cnt = 0, mount = 0;
status s;
for (i = 0; i < 12; i++)
{
for (j = 0; j < 12; j++)
{
if (map[i][j] < 0)
{
s.addNode(Node(i, j, map[i][j], 'A' + cnt));
cnt++;
mount += map[i][j];
}
}
}
if (cnt == 0) return;
char way[30];
walkPath[0] = 0;
crt_step = 0;
Node c = courier;
if (mount + courier.mount > 0)
{
for (i = 0; i < s.v_demand.size(); i++)
{
strcat(walkPath, getWay(c, s.v_demand[i], way));
c = s.v_demand[i];
}
}
else
{
for (i = 0; i < s.v_demand.size(); i++)
{
strcat(walkPath, getWay(c, v_denote[0], way));
strcat(walkPath, getWay(v_denote[0], s.v_demand[i], way));
c = s.v_demand[i];
}
}
//out << "in*******" << endl;
// output();
//cout<<"in ***** " << walkPath << endl;
}
int main()
{
minstep = 500;
rltcnt = 0;
char code;
status s, start;
int x, y, mount;
int i = 0;
// cout << "----" << endl;
while (cin >> code)
{
switch (code)
{
case 'S':
cin >> x >> y;
// out << "S\t" << x << "\t" << y << endl;
s.courier = Node(x, y, 100, 'C');
s.addNode(Node(x, y, 5000, 'S'));
break;
case 'R':
cin >> x >> y >> mount;
// out << "R\t" << x << "\t" << y << "\t" << mount << endl;
s.addNode(Node(x, y, mount, 'A' + i));
i++;
if (s.v_demand.size() == 5)
{
start = s;
start.getOnePath();
strcpy(s.path, start.path);
s.getWalkPath();
s.iniMap();
// s.output();
// out << s.path << endl;
// out << s.walkPath << endl;
}
break;
case 'G':
s.walk();
// s.output();
if (s.finish())
{
goto lab;
}
break;
}
}
lab:
return 0;
}
void getBest(status s)
{
stack<status> stk;
status start = s;
s.output();
minstep = s.getOnePath();
s.outputBest();
rltcnt = 0;
v_best.clear();
stk.push(start);
do {
status& top = stk.top();
status next;
if (top.haveNext())
next = top.getNext();
else stk.pop();
if (next.haveNext())
stk.push(next);
} while (!stk.empty());
//out << "best size\t" << v_best.size() << endl;
for (int i = 0; i < v_best.size(); i++)v_best[i].outputBest();
}