#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
int startx, starty, endx, endy;//起点，终点的行标和列标
int k = 0;
bool visit[1000][1000];
int d[1000][1000];
int route[1000];
struct Node
{
int x, y;
Node(int xx = 0, int yy = 0)
{
x = xx;
y = yy;
//this->pre = pre;
}
} vec[1000];
int parent [N*N];//父结点
maze::maze()//构造函数
{
}
maze::maze(int x)//析构函数
{
setN(x);
mazeInit();
}
void maze::print()
{
//Dijkstra();
/*输出迷宫*/
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cout<<mazes[i][j]<<" ";
cout<<endl;
}
}
/*设置迷宫大小*/
void maze::setN(int sizeN)
{
if(sizeN<4)
sizeN=4;
n = sizeN;
m = (n-1)/2;
}
/*获得迷宫大小*/
int maze::getN()
{
return n;
}
/*获得路径长度*/
int maze::getLenPath()
{
return len_path;
}
/*初始化并查集数组，使parent[i]==i*/
void init()
{
//memset(rank, 0, sizeof(rank));
for(int i = 0; i < N*N; i++)
parent[i] = -1;
}
/*函数搜索并返回包含元素X的树的根，递归实现*/
int Find(int x)
{
while(parent[x]>=0) x=parent[x];//循环查找x的根
return x;
}
/*函数求两个不相交的集合的并*/
void Union(int root1, int root2)
{
int r1 = Find(root1);
int r2 = Find(root2);
int temp;
if(r1!=r2)
{
temp =parent[r1]+parent[r2];
if(parent[r2]<parent[r1])
{
parent[r1]=r2;
parent[r2]=temp;
}
else
{
parent[r2]=r1;
parent[r1]=temp;
}
}
}
/*求在二维数组的(x,y)位置上的位置，并将其转化为一维数组下表*/
int tolist(int x, int y, int n)
{
return x*n+y;
}
/************************
0表示墙，非零表示通路*
**********************/
void maze::mazeInit()
{
//随机生成迷宫函数，将生成的函数保存在maze二维数组中
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
mazes[i][j] = 0;//不可走
init();//初始化并查集数组
for(int i = 1; i <n-1; i++)
{
if(i%2==1)//（i,j）均为奇数全部置1
for(int j = 1; j <n-1; j+=2)
mazes[i][j] = 1;//可走
}
//print();
//cout<<"*******************"<<endl;
int sx, sy, ex, ey, x, y;
srand(time(NULL));//设置一个随机种子，每次运行都能保证随机种子不同
int d;
int tx1, ty1, tx2, ty2;
sx = sy = 1;
if(n%2==0)
{
ex = ey = n-3;
}
else
{
ex = ey = n-2;
}
//cout<<"测试"<<endl;
/**************************************************************
*实现步骤： *
*—①随机选择一条边，判断边连接的顶点，是否在同一子树中，如果 *
*是则执行③，如果不是则执行②。 *
*—②连通这两个顶点，并把他们任意一个添加到另一个所在的子树中 *
*—③判断起点和终点是否在同一子树中，如果不是则执行①，如果是 *
*则退出。 *
****************************************************************/
int flag=0;
while(1)
{
//判断起点和终点是否在同一子树中,如果是则退出,并且为连通图。
do
{
//当随机产生的迷宫中的点是通路时，循环，随机产生点(x,y)
x = rand()%(n-2)+1;//围墙内部的点
y = (rand()+123)%(n-2)+1;
}
while(mazes[x][y] !=0);//为0时退出循环
d = x%2;//记录下行值的奇偶
if(!d)
{
/*d为偶数时，判断该位置上下是否在同一个集合，如果不在就合并
并将该点设置为通路*/
tx1 = x+1;
ty1 = y;
tx2 = x-1;
ty2 = y;
if(Find(tolist(tx1, ty1, n)) != Find(tolist(tx2, ty2, n)))
{
if(mazes[tx1][ty1]==1&&mazes[tx2][ty2]==1)
{
mazes[x][y] = 2;
Union(tolist(tx1, ty1, n), tolist(tx2, ty2, n));
Union(tolist(tx1, ty1, n), tolist(x, y, n));
flag++;
}
}
}
else
{
/*d为奇数时，判断该位置左右是否在同一个集合，如果不在就合并
并将改点设置为通路*/
tx1 = x;
ty1 = y+1;
tx2 = x;
ty2 = y-1;
if(Find(tolist(tx1, ty1, n)) != Find(tolist(tx2, ty2, n)))
{
if(mazes[tx1][ty1]==1&&mazes[tx2][ty2]==1)
{
mazes[x][y] = 2;
Union(tolist(tx1, ty1, n), tolist(tx2, ty2, n));
Union(tolist(tx1, ty1, n), tolist(x, y, n));
flag++;
}
}
}
// print();
// cout<<"*******************"<<endl;
if((flag==m*m-1)&&(Find(tolist(sx, sy, n)) == Find(tolist(ex, ey, n))))
{
break;
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
if(mazes[i][j]==2)
mazes[i][j]=1;
}
}
//print();
//cout<<"*******************"<<endl;
for(int i = 0; i < n; i++)
{
mazes[i][n-1] = 0;//将最后一列设置为非通路
mazes[n-1][i] = 0;//将最后一行设置为非通路
}
if(n%2==0)
{
mazes[n-2][n-2]=1;
mazes[n-2][n-3]=1;
mazes[n-3][n-2]=0;
}
mazes[sx][sy-1] = 2;//入口
mazes[n-2][n-1] = 3;//出口
//print();
}
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
void BFS()
{
queue que;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
d[i][j] = INF; //初始化所有点的距离为INF
que.push(Node(startx, starty));
d[startx][starty] = 0; //从起点出发将距离设为0，并放入队列首端
while (que.size()) //题目保证有路到终点，所以不用担心死循环
{
Node node= que.front(); que.pop();//弹出队首元素
if(Node.first == endx&&Node.second == endy)
{
break; //已经到达终点则退出
}
for (int i = 0; i < 4; i++)
{
int nx = Node.first + dx[i];
int ny = Node.second + dy[i];//移动后的坐标
//判断可移动且没到过
if (0 <= nx&&nx < N
&& 0 <= ny&&ny <N
&&maze[nx][ny] != '#'
&&d[nx][ny] == INF)//之前到过的话不用考虑，因为距离在队列中递增，肯定不会获得更好的解
{
que.push(Node(nx, ny)); //可以移动则设定距离为之前加一，放入队列
d[nx][ny] = d[Node.first][Node.second] + 1;
}
}
}
}
/*void maze::Dijkstra()
{
len_path=0;
queueQ;//存放搜索过程中的位置信息
memset(visit, false, sizeof(visit));
memset(dis, INF, sizeof(dis));
startx=1;
starty=0;
endx=getN()-2;
endy=getN()-1;
dis[startx][starty] = 0;
Q.push(Node(startx, starty, -1));//起点进队
Node t;
int r[4][2] = { {-1,0},{0,1},{0,-1},{1,0} };//方向
while (!Q.empty())
{
t = Q.front();//t=队首
vec[k++] = t;//vec[k++]=队首
visit[t.x][t.y] = true;//标记
if (t.x == endx && t.y == endy)
break;//终点跳出
for (int i = 0; i < 4; i++)//上下左右依次进队
{
int x = t.x + r[i][0];//左上下右
int y = t.y + r[i][1];
if (!visit[x][y] && mazes[x][y])//判断是否可以进队
{
if (dis[x][y] > dis[t.x][t.y] + 1)
{
dis[x][y] = min(dis[x][y], dis[t.x][t.y] + 1);
Q.push(Node(x, y, k - 1));//压进队尾
}
}
}
Q.pop();//弹出队首
}
route[0] = k - 1;
k = 1;
while (t.pre != -1)
{
route[k++] = t.pre;
t = vec[t.pre];
}
//len=0;
//求最短路径
for(int i= k-1;i>=0;i--)
{
len_path++;
}
return;
}*/
void maze::printPath()//输出迷宫路径
{
BFS();
//Dijkstra();
for(int i = len_path-1; i >= 0; i--)
{
if(mazes[vec[route[i]].x][vec[route[i]].y]==1)
{
mazes[vec[route[i]].x][vec[route[i]].y] = 4;
}
}
}
void maze::recoverPath()
{
for(int i = len_path-1; i >= 0; i--)
if(mazes[vec[route[i]].x][vec[route[i]].y]==4)
mazes[vec[route[i]].x][vec[route[i]].y] = 1;
}
void maze::fileout()
{
double t =getTime();
BFS();
//Dijkstra();
/*输出到文件*/
ofstream SaveFile("C:\Users\PC\Desktop\mazePath.txt");
SaveFile<<"路径："<
for (int i = k-1; i >= 0; i--)
{
SaveFile << '(' <<vec[route[i]].x << ',' << vec[route[i]].y << ')';
//cout<< '(' <<vec[route[i]].x << ',' << vec[route[i]].y << ')'<<endl;//测试
}
SaveFile << endl;
SaveFile << "路径长度：" <<getLenPath()<< endl;
SaveFile << "找路时间：" <<t<<"ms"<<endl;
//测试
SaveFile.close();
}
double maze::getTime()
{
//recoverPath();//确定没有执行过寻找路径
time_t start=0, finish;
start = clock();
//printPath();
BFS();
//Dijkstra();
finish =clock();
double time=(double)(finish-start);
return time;
}
出现的问题是
error:expected primary-expression before '_' token
【第一次提问瑟瑟发抖，求大佬解答
