migong.c

c语言一些基础编码

/* 标准文档模板 */

#include "Stdio.h"
#include "Conio.h"

/*迷宫问题*/
#define M2 12
#define N2 11
#define MAXLEN M2
#define True  1
#define False 0
#define Null 0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

int M=M2-2,N=N2-2;


typedef struct elem
 {
  int x,y,dir;
 } ElemType;

typedef struct stktag
 {
   ElemType stack[MAXLEN];
   int top;
 } STACK;

typedef struct moved
 {
  int dx,dy;
 }MOVE;

void IniMaze(int maze[][N2]); /*初始化迷宫*/
void IniMove(MOVE move[]);
void IniStack(STACK *s);
int  Push(STACK *s,ElemType x);
ElemType Pop(STACK *s);
void path(int maze[][N2],MOVE move[],STACK *s);
void draw(int maze[][N2],STACK *s);

void main() /* 寻找迷宫通路程序*/
{
 STACK *s;
 int maze[M2][N2];
 MOVE move[8];
 IniMaze(maze); /* 初始化迷宫数组 */
 getch();
 s=(STACK *)malloc(sizeof(STACK));
 IniStack(s);
 IniMove(move);
 path(maze,move,s);
 draw(maze,s);

}/* main */

void IniMaze(int maze[][N2]) /*初始化迷宫*/
{
 int i,j,num;
 for(i=0,j=0;i<=M+1;i++)
    maze[i][j]=1;
 for(i=0,j=N+1;i<=M+1;i++)
    maze[i][j]=1;
 for(i=0,j=0;j<=N+1;j++)
    maze[i][j]=1;
 for(i=M+1,j=0;j<=N+1;j++)
    maze[i][j]=1;
 for(i=1;i<=M;i++)
 {
  for(j=1;j<=N;j++)
  {
   num=(800*(i+j)+1500) % 327;
   if ((num<150)&&(i!=M||j!=N))
     maze[i][j]=1;
   else
    maze[i][j]=0;
  }
 }
 printf("\n");
 for(i=0;i<=M+1;i++)
 {
  printf("\n");
  for(j=0;j<=N+1;j++)
  {
   if((i==0)&&(j==0)||(i==M+1)&&(j==N+1)) printf("%3d",0);
   else printf("%3d",maze[i][j]);
  }
 }

}/* IniMaze */

void IniMove(MOVE move[])
{
 move[0].dx=0; move[0].dy=1;
 move[1].dx=1; move[1].dy=1;
 move[2].dx=1; move[2].dy=0;
 move[3].dx=1; move[3].dy=-1;
 move[4].dx=0; move[4].dy=-1;
 move[5].dx=-1; move[5].dy=-1;
 move[6].dx=-1; move[6].dy=0;
 move[7].dx=-1; move[7].dy=1;

} /* IniMove */

void IniStack(STACK *s)
{
 s->top=-1;
}/* IniStack */

int Push(STACK *s,ElemType x)
{
 if(s->top==MAXLEN-1)
  return (False);
 else
 {
   s->stack[++s->top]=x;
   return (True);
 }
}
/* Push */

ElemType Pop(STACK *s)
{
 ElemType elem;
 if(s->top<0)
 {
  elem.x=Null;
  elem.y=Null;
  elem.dir=Null;
  return (elem);
 }
 else
 {
  s->top--;
  return (s->stack[s->top+1]);
 }
}/* pop */

void path(int maze[][N2],MOVE move[],STACK *s)
{
  int i,j,dir,x,y,f;
  ElemType elem;
  i=1;
  j=1;
  dir=0;
  maze[1][1]=-1; /* 设[1][1]为入口处 */
  do
  {
    x=i+move[dir].dx;  /* 求下一步可行的到达点的坐标 */
    y=j+move[dir].dy;
    if(maze[x][y]==0)
     {
       elem.x=i;
       elem.y=j;
       elem.dir=dir;
       f=Push(s,elem);
       if(f==False) printf("栈长度太短\n");
       i=x;
       j=y;
       dir=0;
       maze[x][y]=-1;
     }
    else
     if(dir<7) dir++;
     else
      {      /* 8个方向都不可行,就退回一步 */
       elem=Pop(s);
       if(elem.x!=Null)
       {
       i=elem.x;
       j=elem.y;
       dir=elem.dir+1;
       }
      }
  }while(!( (s->top==-1) && (dir>=7) || (x==M)&&(y==N)&&(maze[x][y]==-1)));

  if(s->top==-1)
    printf("此迷宫无路\n");
  else
  {
   elem.x=x;elem.y=y;elem.dir=dir;
   f=Push(s,elem);
   printf("\n迷宫的通路是:\n");
   i=0;
   while(i<=s->top)
   {
     printf("(%d,%d)",s->stack[i].x,s->stack[i].y); /* 显示迷宫通路 */
     if(i!=s->top)
       printf("-->");
     if((i+1)%4==0)
      printf("\n");
     i++;
   }
  printf("\n");
  }
 }/* path */

void draw(int maze[][N2],STACK *s)
{
 int i,j;
 ElemType elem;
 for(i=1;i<=M;i++) /* 将迷宫中全部的-1值恢复为0值 */
 for(j=1;j<=N;j++)
  if(maze[i][j]==-1)
     maze[i][j]=0;
 while(s->top>-1)/* 根据栈中元素的坐标,将通路的各个点的值改为8 */
 {
  elem=Pop(s);
  i=elem.x;
  j=elem.y;
  maze[i][j]=8;
 }
 for(i=0;i<=M+1;i++)
 {
  for(j=0;j<=N+1;j++)
  {
   if((i==0)&&(j==0)||(i==M+1)&&(j==N+1)) printf("%3d",0);
   else if(maze[i][j]==8) printf("  %c",'*');
    else printf("%3d",maze[i][j]); /* 显示已标记通路的迷宫 */
  }
  printf("\n");
 }
 printf("\n");
}/* draw */