|
简单迷宫（DFS、BFS）
PS：不得不说自己太菜了，DFS和BFS的模板题都搞了好几个小时
一、判断是否能走到问题（DFS）
题目描述
有一个 10 x 10 的迷宫，起点是‘S’，终点是‘E’，墙是‘#’，道路是空格。一个机器人从起点走到终点。当机器人走到一个通道块，前面已经没有路可走时，它会转向到当前面向的右手方向继续走。如果机器人能够过，则留下足迹‘*’，如果走不通，则留下标记‘!’。 下面给出书中的算法，请你模拟机器人的走法输出最终的状态。
输入
一个 10 x 10 的二维字符数组。
输出
机器人走过的路径状态。
样例输入
样例输出
 题解：直接利用DFS算法即可，开始想着在主函数中输出，但是没考虑到在回溯的过程中将原来走过的全都变为了‘!’，（哇，心态爆炸），太菜了，下面就是代码：
#include
using namespace std;
//int dir[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
int dir[4][2]= {{0,1},{1,0},{0,-1},{-1,0}}; //方向
int vis[15][15]; //判断是否走过
char s[15][15];
int x1,x2,y,y2;
void dfs(int x,int y)
{
if(x==x2&&y==y2) //到达终点后，直接输出，避免了回溯导致全都变为'!'
{
s[x][y]='*';
for(int i=0;i
int X=x+dir[k][0];
int Y=y+dir[k][1];
if((s[X][Y]==' '||s[X][Y]=='E')&&vis[X][Y]==0&&X>=0&&X=0&&Y
memset(vis,0,sizeof(vis));
for(int i=0; i
scanf("%c",&s[i][j]);
if(s[i][j]=='S')
{
x1=i;
y=j;
}
if(s[i][j]=='E')
{
x2=i;
y2=j;
}
}getchar();
}
//for(int i=0;i1,0},{0,-1},{-1,0}};
int sx,sy,ex,ey;
int t;
int tx,ty;
int front,rear,flag;
int i,j;
struct note
{
int x;
int y;
int s;
};
struct note que[110*110];
void bfs()
{
vis[sx][sy] = 1;
front = 1;
rear = 1;
flag = 0;
que[rear].x = sx;
que[rear].y = sy;
que[rear].s = 0;
rear++;
while(front
tx = que[front].x + dir[i][0];
ty = que[front].y + dir[i][1];
if(tx n||ty m)
continue;
if(!vis[tx][ty]&&str[tx][ty]!='#')
{
vis[tx][ty] = 1;
que[rear].x = tx;
que[rear].y = ty;
que[rear].s = que[front].s +1;
rear++;
}
if(tx == ex&&ty == ey)
{
flag = 1;
break;
}
}
if(flag == 1)
{
break;
}
front++;
}
if(flag == 0)
printf("-1\n");
else
printf("%d\n",que[rear-1].s);
}
int main()
{
scanf("%d",&t);
while( t --)
{
scanf("%d%d",&n,&m);
getchar();
memset(vis,0,sizeof(vis));
for(i = 1; i
scanf("%c",&str[i][j]);
if(str[i][j] == 'S')
{
sx = i;
sy = j;
}
if(str[i][j] == 'E')
{
ex = i;
ey = j;
}
}
getchar();
}
bfs();
}
return 0;
}
还是做题做少了，最近得好好做做数据结构相关题了！！！！
|