高速路网-爱来自第三学期
高速路网-爱来自第三学期
这是一个项目题。
题目描述
题意分析
分为2个部分： 1.将图片转换为Graph 2.对Graph进行次短路算法
实现思路：
1.将图片转换为Graph
1.对读取的PNG进行广度优先染色，相同颜色的标一个id，并将每一个州的中心点记录 2.对染色后的地图的每一个州进行六个方向的查询，进行建边
2.次短路
使用迷阵题的代码，注意如果有多条最小路径，不能输出最小路径，要输出次小路径。 使用优先队列优化时间。
代码：
小学期结束后填坑。
https://se.jisuanke.com/_996/graph_lab（已填坑）
#include "state.h"
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <set>
void init_State(struct State *s)
{
s->industry = nullptr;
s->pre = nullptr;
s->count = 0;
s->cord.push_back({0, 0});
s->mind = 0;
s->Edge.clear();
// TODO
}
void delete_State(struct State *s)
{
// TODO
delete[] s->industry;
delete[] s->pre;
std::vector<std::vector<edge>>().swap(s->Edge);
std::vector<std::pair<int, int>>().swap(s->cord);
}
void parse(struct State *s, struct PNG *p)
{
// TODO
// 即统计图片中联通块的个数，或者叫做统计州
// s中要存所有州的信息，以及他们的相邻关系
// 便于后续查找最短路径
// p->image 为读入的位图数据
// 思路：循环对每个结点进行编号
// 对每个结点进行6个方向的循环加边
// p->image max_size 5000*5000
// -1代表白色 -2代表黑色 1-n代表该像素块属于的编号
int *ids = new int[p->width * p->height]();
int id = 1;
for (int y = 0; y < p->height; y++)
{
for (int x = 0; x < p->width; x++)
{
if (ids[y * p->width + x] == 0)
{
PXL *pixel = get_PXL(p, x, y);
if (pixel->blue == 0 && pixel->green == 0 && pixel->red == 0)
{ // black
int tmpx, tmpy;
color(p, ids, -1, x, y, tmpx, tmpy);
}
else if ((pixel->red == 255 && pixel->blue == 255 && pixel->green == 255))
{ // white
int tmpx, tmpy;
color(p, ids, -2, x, y, tmpx, tmpy);
}
else
{ // 正常格子
int tmpx, tmpy;
color(p, ids, id, x, y, tmpx, tmpy);
s->cord.push_back({tmpx, tmpy});
id++;
}
}
}
}
// 染色标记完毕
// 开始记录每个州的发达程度industry
s->count = id - 1;
s->industry = new int[s->count + 1]();
s->Edge.resize(s->count + 1);
for (int y = 0; y < p->height; y++)
{
for (int x = 0; x < p->width; x++)
{
if (ids[y * p->width + x] != -1 && ids[y * p->width + x] != -2)
{
int _id = get_id(ids, x, y, p->width, p->height);
if (s->industry[_id] != 0)
{
continue;
}
PXL *pixel = get_PXL(p, x, y);
s->industry[_id] = cal_industry(pixel);
}
}
}
// 对每个州进行六方向连接 建边 标记某个顶点是否已经扩展好边
int dir[6][2] = {
{-8, 0}, {8, 0}, {-4, -8}, {4, -8}, {-4, 8}, {4, 8}};
for (size_t i = 1; i <= s->count; i++)
{
std::pair<int, int> cord = s->cord[i];
for (int j = 0; j < 6; j++)
{
int tx = cord.first + dir[j][0];
int ty = cord.second + dir[j][1];
if (in(tx, ty, p->width, p->height))
{
int toid = get_id(ids, tx, ty, p->width, p->height);
if (toid != 0 && toid != -1 && toid != -2)
{
s->Edge[i].push_back({toid, s->industry[toid], 1});
}
}
}
}
#ifdef DEBUG
for (int i = 1; i <= s->count; i++)
{
printf("(%d,%d) ", s->cord[i].first, s->cord[i].second);
}
puts("");
#endif // 打印每个州的中心点
#ifdef DEBUG
int cnt = 0;
for (int i = 1; i <= s->count; i++)
{
for (edge node : s->Edge[i])
{
printf("%d %d %d\n ", i, node.v, node.w);
cnt++;
}
}
printf("%d %d\n", s->count, cnt);
#endif // 打印每个顶点的邻接表
#ifdef DEBUG
for (int i = 1; i <= s->count; i++)
{
std::cout << s->industry[i] << " ";
}
puts("");
#endif // 打印每个州的发达程度
#ifdef DEBUG
for (int i = 0; i < p->height; i++)
{
for (int j = 0; j < p->width; j++)
{
std::cout << std::setw(5) << ids[i * p->width + j] << " ";
}
puts("");
}
#endif // 打印染色后的图
delete[] ids;
}
int solve1(struct State *s)
{
int ans = dij2(s, 1);
return ans;
}
int solve2(struct State *s)
{
// TODO
if (s->pre == nullptr)
{
solve1(s);
}
int *path = new int[s->count + 1]();
int pathid = 0;
getpath(path, s->count, pathid, s->pre);
#ifdef DEBUG_PATH
printf("----This is Shortest PATH----\n");
for (int i = 0; i < pathid; i++)
{
printf("%d", path[i]);
if (i != pathid - 1)
{
printf("->");
}
}
puts("");
printf("-----------------------------\n");
#endif
long long ans = 0x3f3f3f3f;
for (int i = 0; i < pathid - 1; i++)
{
int u = path[i];
int v = path[i + 1];
for (edge &e : s->Edge[u])
{
if (e.v == v)
{
e.f = 0;
}
}
// int *pre = nullptr;
long long tmp = dij2(s, 0); // ans
// int *tmppath = new int[s->count + 1]();
// int tmpid = 0;
// getpath(tmppath, s->count, tmpid, pre);
#ifdef DEBUG_TMP_PATH
printf("----This is the Second Shortest PATH----\n");
for (int i = 0; i < tmpid; i++)
{
printf("%d", tmppath[i]);
if (i != tmpid - 1)
{
printf("->");
}
}
printf(" value:%d",tmp);
puts("");
printf("-----------------------------\n");
#endif
// delete[] tmppath;
if (ans > tmp)
{
if(s->mind&&tmp>s->mind)
{
ans = tmp;
}
}
for (edge &e : s->Edge[u])
{
if (e.v == v)
{
e.f = 1;
}
}
}
delete[] path;
return ans;
}
// long long dij3(struct State *s, int *(&pre))
// {
// if (pre == nullptr)
// {
// pre = new int[s->count + 1]();
// }
// struct node
// {
// long long dis, u;
// bool operator>(const node &a) const { return dis > a.dis; }
// };
// const long long inf = 0x3f3f3f3f;
// long long *dis = new long long[s->count + 1];
// int *vis = new int[s->count + 1]();
// std::priority_queue<node, std::vector<node>, std::greater<node>> q;
// for (size_t i = 0; i < s->count + 1; i++)
// {
// dis[i] = inf;
// }
// dis[1] = 0;
// q.push({0, 1});
// while (!q.empty())
// {
// int u = q.top().u;
// q.pop();
// if (vis[u])
// continue;
// vis[u] = 1;
// for (auto ed : s->Edge[u])
// {
// int v = ed.v, w = ed.w;
// if (ed.f)
// {
// if (dis[v] > dis[u] + w)
// {
// dis[v] = dis[u] + w;
// pre[v] = u;
// #ifdef DEBUG_DIJPATH
// printf("%d->%d:%d\n", u, v, w);
// #endif
// q.push({dis[v], v});
// }
// }
// }
// }
// #ifdef DEBUG_1
// for (int i = 0; i < s->count; i++)
// {
// printf("pre[%d]:%d ", i, s->pre[i]);
// }
// #endif
// long long ans = dis[s->count];
// delete[] vis;
// delete[] dis;
// return ans;
// }
long long dij2(struct State *s, int opt)
{
if (s->pre == nullptr && opt)
{
s->pre = new int[s->count + 1]();
}
struct node
{
long long dis, u;
bool operator>(const node &a) const { return dis > a.dis; }
};
const long long inf = 0x3f3f3f3f;
long long *dis = new long long[s->count + 1];
int *vis = new int[s->count + 1]();
std::priority_queue<node, std::vector<node>, std::greater<node>> q;
for (size_t i = 0; i < s->count + 1; i++)
{
dis[i] = inf;
}
dis[1] = 0;
q.push({0, 1});
while (!q.empty())
{
int u = q.top().u;
q.pop();
if (vis[u])
continue;
vis[u] = 1;
for (auto ed : s->Edge[u])
{
int v = ed.v, w = ed.w;
if (ed.f)
{
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if (opt)
{
s->pre[v] = u;
#ifdef DEBUG_DIJPATH
printf("%d->%d:%d\n", u, v, w);
#endif
}
q.push({dis[v], v});
}
}
}
}
#ifdef DEBUG_1
for (int i = 0; i < s->count; i++)
{
printf("pre[%d]:%d ", i, s->pre[i]);
}
#endif
long long ans = dis[s->count];
if(opt)
{
s->mind = ans;
}
delete[] vis;
delete[] dis;
return ans;
}
/// @brief 获取路径
/// @param path 路径存入path
/// @param x 从x往前推
/// @param pathid path大小存入pathid
/// @param pre 前驱结点数组
void getpath(int *path, int x, int &pathid, int *pre)
{
if(pre==nullptr)
{
return;
}
if (x == 1)
{
path[pathid++] = x;
return;
}
getpath(path, pre[x], pathid, pre);
path[pathid++] = x;
}
inline bool in(int x, int y, int width, int height)
{
return x >= 0 && x < width && y >= 0 && y < height;
}
// aid function
// 对图进行染色 用来标记id
void color(struct PNG *p, int *map, const int id, const int sx, const int sy, int ¢er_x, int ¢er_y)
{
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
int max_x = -1, max_y = -1;
int min_x = INT_MAX, min_y = INT_MAX;
std::queue<std::pair<int, int>> q;
q.push({sx, sy});
PXL *origin_pxl = get_PXL(p, sx, sy);
map[sy * p->width + sx] = id;
while (!q.empty())
{
std::pair<int, int> coordinate = q.front();
q.pop();
max_x = max(max_x, coordinate.first);
max_y = max(max_y, coordinate.second);
min_x = min(min_x, coordinate.first);
min_y = min(min_y, coordinate.second);
for (int i = 0; i < 4; i++)
{
int tx = coordinate.first + dir[i][0];
int ty = coordinate.second + dir[i][1];
if (in(tx, ty, p->width, p->height))
{
PXL *pixel = get_PXL(p, tx, ty);
if ((*pixel == *origin_pxl) && map[ty * p->width + tx] == 0)
{
map[ty * p->width + tx] = id;
q.push({tx, ty});
}
}
}
}
center_x = (max_x + min_x) / 2;
center_y = (max_y + min_y) / 2;
}
int get_id(int *ids, int x, int y, int width, int height)
{
if (!in(x, y, width, height))
{
return 0;
}
return ids[y * width + x];
}
int cal_industry(PXL *pxl)
{
return (255 * 255 * 3 - pxl->red * pxl->red - pxl->green * pxl->green - pxl->blue * pxl->blue);
}
int max(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int min(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
