| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 566 人关注过本帖
标题:问题求解大虾帮忙
只看楼主 加入收藏
rainbowbin
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2008-7-8
收藏
 问题点数:0 回复次数:0 
问题求解大虾帮忙
怎么修改可以得出迷宫最短路径?

程序代码:
#include "stdio.h"
#define StackSize 100

typedef struct{
  int i,j;
}PosType;

typedef struct{
  PosType pos;
  int di;
} ElemType;

typedef struct {
  ElemType elem[StackSize];
  int top;
}SqStack;

InitStack(SqStack *pS)
{
  pS->top=0; /* top指向栈顶的上一个元素 */
}

int Push(SqStack *pS,ElemType e)
{
  if (pS->top==StackSize-1)   /* 栈满 */
    return 0;

  pS->elem[pS->top]=e;
  pS->top=pS->top+1;
  return 1;
}

int Pop(SqStack *pS,ElemType* pe)
{
  if (pS->top==0)  /* 栈空 */
    return 0;

  pS->top = pS->top - 1;
  *pe = pS->elem[pS->top];
  return 1;
}

main()
{
  SqStack S;
  ElemType e;
  PosType pos,pos_end;
  int maze[10][10]={      /* 离散迷宫矩阵,0表示墙壁 */
    {0,0,0,0,0,0,0,0,0,0},
    {0,1,1,0,1,1,1,0,1,0},
    {0,1,1,0,1,1,1,0,1,0},
    {0,1,1,1,1,0,0,1,1,0},
    {0,1,0,0,0,1,1,1,1,0},
    {0,1,1,1,0,1,1,1,1,0},
    {0,1,0,1,1,1,0,1,1,0},
    {0,1,0,0,0,1,0,0,1,0},
    {0,0,1,1,1,1,1,1,1,0},
    {0,0,0,0,0,0,0,0,0,0}
  };
  int i,j;

  InitStack(&S);
  pos_end.i=8;pos_end.j=8;
  pos.i=1;pos.j=1;

  do {
    if (maze[pos.i][pos.j]==1) {  /* 当前位置不是墙壁并且没走过 */
      maze[pos.i][pos.j]=2;   /* 标记已走过 */
      e.pos = pos;
      e.di = 1;
      Push(&S,e);           /* 加入路径 */
      if (pos.i==pos_end.i && pos.j==pos_end.j)     /* 如果已经到达终点,退出循环,求得的路径放在栈中 */
        break;
      else
        pos.j++;            /* 下一个位置是当前位置的右邻 */
    }
    else{  /* 当前位置不能通过 */
      if(S.top>0){
        Pop(&S,&e);
        while(e.di==4 && S.top>0){
          maze[e.pos.i][e.pos.j]=-1;  /* 留下不能通过的标记,并退回一步 */
          Pop(&S,&e);
        }
        if (e.di<4){
          e.di++; Push(&S,e);      /* 换下一个方向搜索 */
          pos.i=e.pos.i; pos.j=e.pos.j;
          if (e.di==2) pos.i++;    /* 设定当前位置是该方向上的相邻块“右下左上” */
          else if (e.di==3) pos.j--;
          else if (e.di==4) pos.i--;
        }
      }
    }
  }while(S.top>0);


  /* 求得的路径放在栈中 */
  printf("\n");
  while(Pop(&S,&e))
    printf("\n(%d,%d)",e.pos.i,e.pos.j);


  /* 打印出整个迷宫,2的是所找到的路径,-1是走过的不通的路径 */
  printf("\n\n");
  for(i=0;i<10;i++) {
    for(j=0;j<10;j++)
      printf("%2d ",maze[i][j]);
    printf("\n");
  }

  getch();
}
搜索更多相关主题的帖子: 问题求解 top int 
2008-07-09 13:07
快速回复:问题求解大虾帮忙
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021900 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved