为啥要这么定义pos？都没怎么看懂，，，和普通01迷宫有点差别，，生成全联通迷宫找最短路径，，求大佬注释55
#include "pch.h"// pch.cpp: 与预编译标头对应的源文件；编译成功所必需的
#define INT_N 999
#define MAX_DIS 2147483647
using namespace std;//using声明，使程序可以使用程序包含的任何标准C++头文件中的所有名字
Node::Node()
{
}
Node::~Node()//析构函数
{
}
int Graph::findEdge(int node)//找所有节点边的位置
{
int pos = node / N * (N - 1) + node % N;//定义一个节点的行值
int e = 0;
if (node%N == 0)//无左邻居
{
if (row[pos])
e |= Right;//就向右插边
}
else if (node%N == N - 1)//无右邻
{
if (row[pos - 1])
e |= Left;//就向左插边
}
else
{
if (row[pos])
e |= Right;
if (row[pos - 1])
e |= Left;
}
int p2 = (node%N)*(N - 1) + node / N;//定义节点的列值
if (node < N) {
//无上邻居
if (col[p2])
e |= Down;//可以向下插边
}
else if (node >= N * (N - 1)) {
//无下邻
if (col[p2 - 1])
e |= Up;//可以向上插边
}
else {
if (col[p2])
e |= Down;
if (col[p2 - 1])
e |= Up;
}
return e;//返回节点的边，存在e里，得到所有边的位置
}
void Graph::make_rand(int * a)
{
int p = rand() % 4;
int q = rand() % 4;
if (p != q)
{
int n = a[p];
a[p] = a[q];
a[q] = n;
}
}
int Graph::findNode(int node, int Direction)
{
if (Direction & Left)
{
if (node%N != 0) return node - 1;
else return -1;
}
else if (Direction & Right)
{
if (node%N == N - 1) return -1;
else return node + 1;
}
else if (Direction &Up)
{
node = node - N;
if (node < 0) return -1;
return node;
}
else if (Direction & Down)
{
node = node + N;
if (node > N*N - 1) return -1;
return node;
}
return -1;
}
int Graph::findNode2(int node, int Direction)
{
int pos = node / N * (N - 1) + node % N;
int pos2 = (node%N)*(N - 1) + node / N;
if (Direction & Left) {
if (node%N != 0 && row[pos - 1]) return node - 1;
else return -1;
}
else if (Direction & Right) {
if (node%N != (N - 1) && row[pos]) return node + 1;
else return -1;
}
else if (Direction &Up) {
node = node - N;
if (node >= 0 && col[pos2 - 1]) return node;
return -1;
}
else if (Direction & Down) {
node = node + N;
if (node > N*N - 1) return -1;
if (col[pos2]) return node;
return -1;
}
return -1;
}
void Graph::addEdge(int node, int Direction)
{
if (Direction & Left || Direction & Right) {
//左右方向--
int pos = node / N * (N - 1) + node % N;
if ((Direction & Left) && node%N != 0) row[pos - 1] = true;
if ((Direction & Right) && node%N != N - 1) row[pos] = true;
}
if (Direction & Up || Direction & Down) {
//上下方向--
int p2 = (node%N)*(N - 1) + node / N;
if ((Direction & Down) && node < N*(N - 1)) col[p2] = true;
if ((Direction &Up) && node > (N - 1)) col[p2 - 1] = true;
}
}
void Graph::insertEdge(int from)
{
//从from起 插入条边
bool add = false;
for (int start = from; start < 2 * N*(N - 1); start++) {
int pos = 0;
int r = start / (2 * N - 1);
int c = start % (2 * N - 1);
if (c > N - 1) {
//列
pos = (c - (N - 1))*(N - 1) + r;
if (col[pos] == false) {
col[pos] = true;
//add = true;
return;
}
}
else {
//行
pos = r * (N - 1) + c;
if (row[pos] == false) {
row[pos] = true;
return;
}
}
}
for (int start = from; start >= 0; start--) {
int pos = 0;
int r = start / (2 * N - 1);
int c = start % (2 * N - 1);
if (c > N - 1) {
//列
pos = (c - (N - 1))*(N - 1) + r;
if (col[pos] == false) {
col[pos] = true;
//add = true;
return;
}
}
else {
//行
pos = r * (N - 1) + c;
if (row[pos] == false) {
row[pos] = true;
return;
}
}
}
}
void Graph::test(int node)
{
int e = findEdge(node);
printf("node=%d,Up=%d,Down=%d,Left=%d,Right=%d", node, e&Up, e&Down, e&Left, e&Right);
}
Graph::Graph(int n)
{
N = n;
if (N < 2) N = 2;
row = new bool[N*(N - 1)];
col = new bool[N*(N - 1)];
}
Graph::~Graph()
{
delete col;
delete row;
}
bool Graph::travel(int start, vector<int> & visit, bool * have)
{
int count = N * N;
int order[4] = { Left,Right,Up,Down };
int c = 0;
int node2 = 0;
while (visit.size() < count) {
if (c == 0) { c = 1; }
else start = visit.back();
//随机找一个方向开始--
make_rand(order);
bool insert = false;
for (int j = 0; j < 4; j++) {
node2 = findNode(start, order[j]);
if (node2 >= 0 && have[node2] == false) {
visit.push_back(node2);
have[node2] = true;
addEdge(start, order[j]);//添加这个方向的边
insert = true;
break;
}
}
if (insert == false) return false;
}
return true;
}
void Graph::create()
{
srand((unsigned)time(NULL));
int total = N * N;
bool * have = new bool[total];
int i = 0;
for (i = 0; i < total; i++) have[i] = false;
for (i = 0; i < N*(N - 1); i++) {
row[i] = false; col[i] = false;
}
vector<int> visit;//已访问的节点表
vector<int> starts;//起点表
int start = rand() % total;
visit.insert(visit.end(), start);
have[start] = true;
starts.push_back(start);
bool ok = travel(start, visit, have);
while (ok == false) {
start = visit[rand() % visit.size()];
int nRet = std::count(starts.begin(), starts.end(), start);
if (nRet > 0) {
for (int j = 0; j < visit.size(); j++) {
start = visit[j];
nRet = std::count(starts.begin(), starts.end(), start);
if (nRet == 0) break;
}
}
ok = travel(start, visit, have);
starts.push_back(start);
}
//随机 添加一部分边--
int max = 2 * N * (N - 1);
int min = N * N - 1;
int need = (max + min) / 2;
for (int k = min; k <= need; k++) {
//--暂时留空--
int edge = rand() % max;//随机增加的边
//随机找一个起点，增加一个边
insertEdge(edge);
}
delete have;
}
void Graph::print() {
int i, pos, pos2;
char buf[300];
char buf2[300];
char buf3[10];
int max = N * N - 1;
sprintf_s(buf3, "%d", max);
int len = strlen(buf3);
memset(buf3, 0, 10);
for (i = 0; i < N*N; i++) {
if (i%N == 0) {
if (i > 0) {
printf("%s\n", buf);
printf("%s\n", buf2);
}
memset(buf, 0, 300);
memset(buf2, 0, 300);
memset(buf3, 0, 10);
}
if (len == 1) sprintf_s(buf3, "%d", i);
else if (len == 2) sprintf_s(buf3, "%02d", i);
else if (len == 3) sprintf_s(buf3, "%03d", i);
else if (len == 4) sprintf_s(buf3, "%04d", i);
else {
printf("too big");
return;
}
strcat_s(buf, buf3);
pos = i / N * (N - 1) + i % N;//(N-1);
if (i%N != (N - 1)) {
if (row[pos]) strcat_s(buf, "-");
else strcat_s(buf, " ");
}
pos2 = (i%N)*(N - 1) + i / N;
if (i < N*(N - 1)) {
if (col[pos2]) {
if (len == 1) strcat_s(buf2, "| ");
else if (len == 2) strcat_s(buf2, " | ");
else if (len == 3) strcat_s(buf2, " | ");
else if (len == 4) strcat_s(buf2, " | ");
}
else {
if (len == 1) strcat_s(buf2, " ");
else if (len == 2) strcat_s(buf2, " ");
else if (len == 3) strcat_s(buf2, " ");
else if (len == 4) strcat_s(buf2, " ");
}
}
}
printf("%s\n", buf);
printf("%s\n", buf2);
}
void Graph::print2() {
int i, pos, pos2;
char buf[300];
char buf2[300];
char buf3[10];
int max = N * N - 1;
sprintf_s(buf3, "%d", max);
int len = strlen(buf3);
memset(buf3, 0, 10);
for (i = 0; i < N*N; i++) {
if (i%N == 0) {
if (i > 0) {
printf("%s\n", buf);
printf("%s\n", buf2);
}
memset(buf, 0, 300);
memset(buf2, 0, 300);
memset(buf3, 0, 10);
}
if (len == 1) sprintf_s(buf3, "%d", i);
else if (len == 2) sprintf_s(buf3, "%02d", i);
else if (len == 3) sprintf_s(buf3, "%03d", i);
else if (len == 4) sprintf_s(buf3, "%04d", i);
else {
printf("too big");
return;
}
strcat_s(buf, buf3);
pos = i / N * (N - 1) + i % N;//(N-1);
if (i%N != (N - 1)) {
if (row[pos]) strcat_s(buf, "--");
else strcat_s(buf, " ");
}
pos2 = (i%N)*(N - 1) + i / N;
if (i < N*(N - 1)) {
if (col[pos2]) {
if (len == 1) strcat_s(buf2, "| ");
else if (len == 2) strcat_s(buf2, " | ");
else if (len == 3) strcat_s(buf2, " | ");
else if (len == 4) strcat_s(buf2, " | ");
}
else {
if (len == 1) strcat_s(buf2, " ");
else if (len == 2) strcat_s(buf2, " ");
else if (len == 3) strcat_s(buf2, " ");
else if (len == 4) strcat_s(buf2, " ");
}
}
}
printf("%s\n", buf);
printf("%s\n", buf2);
}
int Graph::edgeCount()
{
int edge = 0;
int Count = N * (N - 1);
for (int i = 0; i < Count; i++) {
if (row[i]) edge++;
if (col[i]) edge++;
}
return edge;
}
void Graph::path(int st, int en) {
if (st == en) {
printf("%d %d", st, en);
return;
}
stack<int> nodes;
stack<int> edges;
int Direction[4] = { Left,Up,Right,Down };
bool * visited = new bool[N*N];
int i = 0;
for (i = 0; i < N*N; i++) visited[i] = false;
nodes.push(st);
edges.push(-1);
visited[st] = true;
//visit.push(st);
while (nodes.empty() == false) {
int n = nodes.top();
int dir = edges.top();
int n2 = -1;
while (dir < 3 && n2 < 0) {//dir={-1,0,1,2}=>{0,1,2,3}
dir++;
n2 = findNode2(n, Direction[dir]);
//是否可通--
if (n2 >= 0) {
if (visited[n2]) n2 = -1;
else break;
}
}
if (n2 < 0) {
visited[n] = false;//退出该节点了
nodes.pop();
edges.pop();
}
else {
edges.pop(); edges.push(dir);
if (n2 == en) {
//找到了--
//stack<int> print = nodes;
nodes.push(n2);
print_stack(nodes);
nodes.pop();
int dir2 = edges.top();
if (dir2 == 3) {
//退栈--
int n3 = nodes.top(); nodes.pop();
edges.pop();
visited[n3] = false;
}
}
else {
nodes.push(n2);
edges.push(-1);
visited[n2] = true;
}
}
}
delete visited;
}
void Graph::shortpath(int st, int en)
{
if (st == en) {
printf("%d %d", st, en);
return;
}
vector< stack<int> > pathes;//所有的路径
int path_len = N * N + 1;//路径长度,最大
stack<int> nodes;
stack<int> edges;
int Direction[4] = { Left,Up,Right,Down };
bool * visited = new bool[N*N];
int i = 0;
for (i = 0; i < N*N; i++) visited[i] = false;
nodes.push(st);
edges.push(-1);
visited[st] = true;
//visit.push(st);
while (nodes.empty() == false) {
//判断当前路径是否超出了最短路径---
if (nodes.size() > path_len) {
int n3 = nodes.top();
visited[n3] = false;
nodes.pop();
edges.pop();
continue;
}
int n = nodes.top();
int dir = edges.top();
int n2 = -1;
while (dir < 3 && n2 < 0) {//dir={-1,0,1,2}=>{0,1,2,3}
dir++;
n2 = findNode2(n, Direction[dir]);
//是否可通--
if (n2 >= 0) {
if (visited[n2]) n2 = -1;
else break;
}
}
if (n2 < 0) {
visited[n] = false;//退出该节点了
nodes.pop();
edges.pop();
}
else {
edges.pop(); edges.push(dir);
if (n2 == en) {
//找到了--
//stack<int> print = nodes;
nodes.push(n2);
if (nodes.size() < path_len) {
pathes.clear();
pathes.push_back(nodes);
path_len = nodes.size();
}
else if (nodes.size() == path_len) {
pathes.push_back(nodes);
}
printf("path_len=%d\n", path_len);
nodes.pop();
int dir2 = edges.top();
if (dir2 == 3) {
//退栈--
int n3 = nodes.top(); nodes.pop();
edges.pop();
visited[n3] = false;
}
}
else {
nodes.push(n2);
edges.push(-1);
visited[n2] = true;
}
}
}
delete visited;
print_pathes(pathes);//输出所有的路径
}
void Graph::print_stack(stack<int> nodes)
{
vector<int> list;
while (nodes.empty() == false) {
list.insert(list.begin(), nodes.top());
nodes.pop();
}
bool first = true;
for (auto val : list)
{
if (first) printf("%d", val);
else printf(" %d", val);
first = false;
}
printf("\n");
}
void Graph::print_stack2(stack<int> path)
{
bool first = true;
while (path.empty() == false)
{
if (first) printf("%d", path.top());
else printf(" %d", path.top());
first = false;
path.pop();
}
printf("\n");
}
void Graph::print_pathes(vector<stack<int>> pathes)
{
for (auto val : pathes) {
print_stack(val);
//printf("\n");
}
}
void Graph::dfs_start()
{
stack<int> path;
bool * visited = new bool[N*N];
for (int i = 0; i < N*N; i++) visited[i] = false;
dfs(visited, path, 0);
print_stack(path);
delete visited;
}
void Graph::dfs(bool * visited, stack<int>& path, int v)
{
int Direction[4] = { Left,Up,Right,Down };
visited[v] = true;
path.push(v);
for (int i = 0; i < 4; i++) {
int n = findNode2(v, Direction[i]);
if (n >= 0 && visited[n] == false) {
dfs(visited, path, n);
}
}
}
void Graph::shortpath2(int from, int to)
{
if (from < 0 || from >= N * N || to < 0 || to >= N * N) {
printf("输入错误。\n"); return;
}
if (from == to) {
printf("%d %d\n", from, to); return;
}
vector<Node> nodes;//节点次序
nodes.resize(N*N);// reserve(N*N);
vector<int> S, U;
//U.resize(N*N);// reserve(N*N);
int i = 0;
for (i = 0; i < N*N; i++) {
//将所有的节点-按次序存入nodes
nodes[i].id = i;
nodes[i].dis = Juli(from, i);
if (nodes[i].dis == 1) {//记下前驱节点
nodes[i].prev.push_back(from);
}
if (i != from) U.push_back(i);//其他节点存入U中
}
int sindex = 0;
S.push_back(from);
//--开始计算过程
while (U.empty() == false) {
vector<int> nodelist;//节点编号表，具体情况查nodes
//int size = S.size();
for (; sindex < S.size(); sindex++) {
//查找u中，距离S[index]最近的节点，形成节点表
int d = MAX_DIS;
for (int u : U) {
if (contains(nodes[u].prev, S[sindex])) {//前驱节点是s[i]
if (nodes[u].dis < d) {
nodelist.clear();
nodelist.push_back(u);
d = nodes[u].dis;
}
else if (nodes[u].dis == d && d != MAX_DIS) {
nodelist.push_back(u);//同样距离的点
}
}
}
//将nodelist的值加入到S中,并从U中去掉
for (int n : nodelist) {
S.push_back(n);
U.erase(std::remove(std::begin(U), std::end(U), n), std::end(U));
}
//--用nodelist的值更新-nodes中的距离和前驱
for (int n : nodelist) {
//
//若-以n为中间节点距离更短，则将nodes中的当前节点的前驱修改为n
for (int u : U) {
int d = Juli(n, u);//计算两点间的距离
if (d != MAX_DIS) {
if (nodes[n].dis + d < nodes[u].dis) {
nodes[u].prev.clear();
nodes[u].prev.push_back(n);//以n为前驱
nodes[u].dis = nodes[n].dis + d;
}
else if (nodes[n].dis + d == nodes[u].dis)
{
//同样距离的点
nodes[u].prev.push_back(n);
}
}
}
}
nodelist.clear();
}
}
//遍历nodes,输出所有的路径--
allpath(from, to, nodes);
}
int Graph::Juli(int from, int to)
{
if (from == to) return 0;
if (findNode2(from, Left) == to) return 1;
if (findNode2(from, Up) == to) return 1;
if (findNode2(from, Right) == to) return 1;
if (findNode2(from, Down) == to) return 1;
return MAX_DIS;
}
bool Graph::contains(vector<int> vec, int val)
{
int nRet = count(vec.begin(), vec.end(), val);
return nRet > 0;
}
void Graph::allpath(int from, int to, vector<Node>& nodes)
{
stack<int> path;
allpath_dfs(path, to, nodes, from);
}
void Graph::allpath_dfs(stack<int>& path, int to, vector<Node>& nodes, int src)
{
path.push(to);
if (to == src) {
print_stack2(path);
path.pop();
return;
}
vector<int> prevlist = nodes[to].prev;//前驱节点
for (int v : prevlist) {
allpath_dfs(path, v, nodes, src);
}
path.pop();
}
int main()
{
int N = 2;
printf("输入边的大小 N=");
scanf_s("%d", &N);
Graph g(N);
g.create();//生成迷宫
g.print();//输出迷宫
printf("\nedge count=%d\n", g.edgeCount());//迷宫现有的边数
/*
g.test(0);
g.test(4);
g.test(10);
*/
g.dfs_start();//深度优先遍历，证明迷宫的连通性
int from=0, to=0;
printf("输入起点:");
scanf_s("%d", &from);
printf("输入终点:");
scanf_s("%d", &to);
printf("计算从%d到%d的最短路径有:\n",from,to);
return 0;
}
