最近在学迷宫问题,这个解法是在网上学的,针对题目做了一点修改但不知道哪错了
#include<iostream>
using namespace std;
int m,n,p,q,minx=99;
char a[100][100];//'.'表示空地,#表示障碍物
int v[100][100];//0表示未访问,1表示访问
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(int x,int y,int step)
{
if(x==p && y==q){
if(step<minx) minx=step;
return ;
}
for(int k=0;k<=3;k++){
int tx,ty;
tx=x+dx[k];
ty=y+dy[k];
if(a[tx][ty]=='.' && v[tx][ty]==0){
v[tx][ty]=1;
dfs(tx,ty,step+1);
v[tx][ty]=0;
}
}
}
int main()
{
int startx,starty;
scanf("%d %d",&m,&n);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
scanf("%c",&a[i][j]);
if(a[i][j]=='@'){
startx=i;
starty=j;
}
if(a[i][j]=='*'){
p=i;
q=j;
}
}
}
v[startx][starty]=1;
dfs(startx,starty,0);
printf("%d",minx);
return 0;
}
少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女**要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由
�
×
�
M×N 个方格组成,有的方格内有可以瞬秒李逍遥的怪物,而有的方格内则是安全。现在李逍遥想尽快找到仙药,显然他应避开有怪物的方格,并经过最少的方格,而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
输入格式
第一行输入两个非零整数
�
M 和
�
N,两者均不大于
20
20。
�
M 表示迷阵行数,
�
N 表示迷阵列数。
接下来有
�
M 行, 每行包含
�
N 个字符,不同字符分别代表不同含义:
- '@':少年李逍遥所在的位置;2) '.':可以安全通行的方格;3) '#':有怪物的方格;4) '*':仙药所在位置。
输出格式
输出一行,该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出
−
1
−1。