2017-03-19

#include

#include

#include

#include

#define MAX_WIDTH    30

#define MAX_HEIGHT   30

typedef struct _step

{

   int x;            //行坐标

   int y;            //列坐标

}STEP;

typedef struct _matrix

{

   int data[MAX_WIDTH+2][MAX_WIDTH+2]; //迷宫数据,0:表示有路,1:表示墙

   int width;                //矩阵(迷宫)的宽,包括最左和最有2堵墙

   int height;                //矩阵(迷宫)的宽,包括顶部和底部2堵墙

   STEP entrance;                //迷宫入口

   STEP exit;                //迷宫出口

}MATRIX;

MATRIX g_matrix=                //初始化为一个迷宫,程序也能从文件中读入迷宫数据

{

   {

       {1, 1, 1, 1, 1, 1, 1},

       {1, 0, 0, 0, 0, 0, 1},

       {1, 1, 0, 1, 0, 1, 1},

       {1, 0, 0, 1, 1, 1, 1},

       {1, 0, 1, 0, 0, 0, 1},

       {1, 0, 0, 0, 1, 0, 1},

       {1, 1, 1, 1, 1, 1, 1},

   },

   7,7,                    //7行,7列,包括4堵墙

   {1,1},                    //入口坐标

   {5,5}                    //出口坐标

};

static STEP  s_shift[]=

{

   {1,0},        //向右走, x++, y 不变

   {0,1},        //向下走,  x 不变, y++

   {-1,0},        //向左走,  x--, y不变

   {0,-1}        //向上走,  x 不变, y--

};

void print_paths(STEP path[],int path_len) //打印走迷宫的路径

{

   int i;

   for (i=0;i

   {

       if (i>0)

           printf("->");

       printf("(%d,%d)",path[i].x, path[i].y);

   }

}

void print_Matrix(MATRIX* pMatrix)        //打印迷宫数据,迷宫数据包含4堵墙

{

   int i,j;

   for (i=0;iheight;i++)

   {

       for (j=0;jwidth;j++)

       {

           if (j!=0)

               printf(" ");

           printf("%d",pMatrix->data[i][j]);

       }

       printf("\n");

   }

}

int search_path(int matric[MAX_WIDTH+2][MAX_WIDTH+2],

               STEP path[],int path_len,STEP exit)

{

   while (1)

   {

       int i,bFind;

       STEP newPos;

for (bFind=0,i=0;i<4;i++)  //从右,下,左,上,查找新的可以走的位置

{

newPos.x = path[path_len-1].x + s_shift[i].x;

newPos.y = path[path_len-1].y + s_shift[i].y;

if ( path_len==1 )

{

if ( g_matrix.data[newPos.x][newPos.y]==0)

{

bFind=1; break; //找到一个位置

}

           }

           // path[path_len-1]表示当前位置,path[path_len-2]表示上一步的位置,

           // 如果新的位置等于上一个位置,将陷入循环,故要求新的位置不能是上一步的位置

           else if ( (newPos.x != path[path_len-2].x || newPos.y!=path[path_len-2].y) && g_matrix.data[newPos.x][newPos.y]==0)

           {

               bFind=1; break;        //找到一个位置

           }

       }

if (bFind)

{

path[path_len++]=newPos; //将新的位置追加到path数组,路径长度+1

if ( newPos.x==exit.x && newPos.y==exit.y)

return path_len;

}

else

{

matric[path[path_len-1].x][path[path_len-1].y]=1; //从当前位置,无路可走,将当前位置标记为墙

path_len--;        //回退一步

if ( path_len==0)

return path_len;

}

}

}

int readMatrix(char *file)

{

   char line[1024];

   FILE *fp=NULL;

   int i,j,x,y;

   fp=fopen(file,"rt");

   if (fp==NULL)

   {

       printf("Can not open file %s\n",file);

       return 0;

   }

   memset(&(g_matrix),0,sizeof(g_matrix));

   fgets(line,sizeof(line)-1,fp);

sscanf(line,"%d %d",&x,&y);                    //读入迷宫的行数和列数

if ( x>MAX_WIDTH || y>MAX_HEIGHT)

{

printf("The Matrix is too large\n");

fclose(fp);

return 0;

}

   g_matrix.width=x+2;                            //在4条边增加4堵墙,故宽和高增加2

   g_matrix.height=y+2;

for (j=0;j

{

g_matrix.data[0][j]=1;                    //第一行为墙

g_matrix.data[g_matrix.height-1][j]=1;    //最后一行为墙

}

   for (i=0;i

   {

       g_matrix.data[i][0]=1;                    //最左边的列为墙

       g_matrix.data[i][g_matrix.width-1]=1;    //最右边的列为墙

   }

for (i=1;i

{

char *p;

fgets(line,sizeof(line)-1,fp);

j=1;

p=line;

while (1)

{

while ( *p==' ' ||*p== 9)//跳过空格符号

p++;

           if ( *p>='0' && *p<='9')

           {

               sscanf(p,"%d",&(g_matrix.data[i][j]));  //读入地i行j列的数据

               while ( *p>='0' && *p<='9')

                   p++;            //数据已经读入,跳过当前的数字

               j++;

           }

           if (j>=g_matrix.width-2)

               break;

       }

   }

fgets(line,sizeof(line)-1,fp);

//读入入口的行坐标和列坐标,和出口的行坐标,列坐标

sscanf(line,"%d %d %d %d",&(g_matrix.entrance.x),&(g_matrix.exit.y),&(g_matrix.exit.x),&(g_matrix.exit.y));

fclose(fp); fp=NULL;

g_matrix.entrance.x++;  //增加了一列是墙,故入口横坐标+1

g_matrix.entrance.y++;  //增加了一行是墙,故入口纵坐标+1

g_matrix.exit.x++;      //增加了一列是墙,故入口横坐标+1

g_matrix.exit.y++;        //增加了一列是墙,故入口纵坐标+1

   return 1;

}

int main()

{

   STEP path[MAX_WIDTH*MAX_HEIGHT];

   int step_count;

   if ( !readMatrix("matrix.txt") )  //不使用初始化的数据,从文件中读入迷宫数据

   {

       return 0;                      //读取失败,直接跳出

}

   printf("The matrix is\n");

   print_Matrix(&g_matrix);

   path[0]=g_matrix.entrance; //将入口位置放入path数组

   step_count = search_path(g_matrix.data,path,1,g_matrix.exit); //查找一条路径,路径的每一步的坐标放入path数组

   if (step_count>0)                          //找到一条出路,步数>0

   {

       printf("\nThe path is\n");

       print_paths(path,step_count);

   }

   else                                 //步数<=0, 没有找到出路

printf("No solution\n");

return 0;

}    

   

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,607评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,047评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,496评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,405评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,400评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,479评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,883评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,535评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,743评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,544评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,612评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,309评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,881评论 3 306
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,891评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,136评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,783评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,316评论 2 342

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,719评论 0 33
  • 第1章 第一个C程序第2章 C语言基础第3章 变量和数据类型第4章 顺序结构程序设计第5章 条件结构程序设计第6章...
    小狮子365阅读 10,573评论 3 71
  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,252评论 0 18
  • 现在的生活节奏快得像加速旋转的风车,我们被推着着往前走。生活中的琐事使我们无法清闲地享受,哪怕一分钟的时间。有时候...
    一辉而明阅读 257评论 0 0
  • 小Q弯着腰在收拾行李,准备我们明天去Z地需要的东西,突然,她抬起脸,用略带感伤的声音问我,“W先生,你喜欢这样的生...
    W先生被占用了阅读 211评论 0 2