数据结构与算法,C/C++ Rescue the princess(拯救公主)
发布网友
发布时间：2022-09-29 23:24
共4个回答
热心网友
时间：2024-12-04 18:20
#include <vector>
#define MAX 100
using namespace std;
struct stack{
int iway,jway;
int direction;
};
stack q[MAX];
int top;
char **arg;//城堡地图指针
char **Mark;//城堡地图mark指针
int FindPrincess(int m,int n,int xW,int yW,int xP,int yP)//找到公主
{
vector<int> ivec;
top=0;
int count=0;//计算找到公主的路径总数
int time=0,MinTime=0;//找到公主所花时间
q[top].iway=xW;
q[top].jway=yW;
q[top].direction=-1;
arg[xW][yW]='s';//'s'标记走过的位置
int i,j,di,find;
while(top>-1)
{
i=q[top].iway;
j=q[top].jway;
di=q[top].direction;
if(i==xP&&j==yP)
{
count++;
for(int val=1;val<top+1;val++)
{
if(Mark[q[val].iway][q[val].jway]=='.'||Mark[q[val].iway][q[val].jway]=='a')
time=time+1;
else if(Mark[q[val].iway][q[val].jway]=='x')
time=time+2;
}
ivec.push_back(time);
if(ivec.size()==1)
{
MinTime=ivec[0];
}
if(ivec.size()>=2)
{
if(ivec[ivec.size()-1]<MinTime)
MinTime=ivec[ivec.size()-1];
}
arg[q[top].iway][q[top].jway]=Mark[q[top].iway][q[top].jway];
top--;
i=q[top].iway;
j=q[top].jway;
di=q[top].direction;
time=0;
}
find=0;
while(find==0&&di<4)
{
di++;
if(di==0&&i==m-1)
di++;
if(di==1&&j==0)
di++;
if(di==2&&i==0)
di++;
if(di==3&&j==n-1)
di++;
switch(di)
{
case(0):i=q[top].iway+1;
j=q[top].jway;
break;
case(1):i=q[top].iway;
j=q[top].jway-1;
break;
case(2):i=q[top].iway-1;
j=q[top].jway;
break;
case(3):i=q[top].iway;
j=q[top].jway+1;
break;
}
if(arg[i][j]=='.'||arg[i][j]=='a'||arg[i][j]=='x')
{
find=1;
}
}
if(find==1)
{
q[top].direction=di;
top++;
q[top].iway=i;
q[top].jway=j;
q[top].direction=-1;
arg[i][j]='s';
}
else
{
arg[q[top].iway][q[top].jway]=Mark[q[top].iway][q[top].jway];
top--;
}
}
if(count==0)
return -1;
else
return MinTime;
}
int main()
{
int m,n;//地图行数与列数
int xWarrior,yWarrior;//勇士坐标
int xPrincess,yPrincess;//公主坐标
int Min;
char **map;
cout<<"请输入城堡N,M(用空格隔开)：";
cin>>m>>n;
//y=n;
cout<<"请输入城堡地图:"<<endl;
map=new char* [m];
Mark=new char* [m+2];
for(int i=0;i<m;++i)
{
map[i]=new char[n];
Mark[i]=new char[n+2];
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>map[i][j];
Mark[i][j]=map[i][j];
if(map[i][j]=='r'||map[i][j]=='R')
{
xWarrior=i;
yWarrior=j;
}
if(map[i][j]=='a'||map[i][j]=='A')
{
xPrincess=i;
yPrincess=j;
}
}
}
arg=map;
Min=FindPrincess(m,n,xWarrior,yWarrior,xPrincess,yPrincess);
cout<<Min;
delete[]Mark;
delete[]map;
return 0;
}
满意请采纳哦！不懂可以问！
热心网友
时间：2024-12-04 18:20
试验任务：
构造一个N行M列的迷宫（可用二维数组表示），并求解：走出迷宫的最短路径（也就是题目中的最短时间，或者叫最短步数）。（勇士r即为迷宫起点，公主a为迷宫终点，在前进过程中，如果遇到怪物x，则步数额外加一）。
热心网友
时间：2024-12-04 18:21
热心网友
时间：2024-12-04 18:21
