Chinaunix首页 | 论坛 | 博客
  • 博客访问: 638988
  • 博文数量: 51
  • 博客积分: 773
  • 博客等级: 军士长
  • 技术积分: 2392
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-07 21:32
文章分类
文章存档

2018年(1)

2013年(16)

2012年(34)

分类: C/C++

2013-10-24 21:30:40

一个迷宫是由N(无限制,你可以取任何值,比如20,50,90,1000等)多个房间组成,每两个相邻的房间之间有可能会有一条通道。这个通道有个神奇的特性,那就是当一个人从一个房间经过某条通道进入到另一个房间后,他身后那条通道会立即消失,同时其他三个方向上可能会出现新的通道,当然也可能没有新通道出现,那就证明这是个死胡同,走不通,但此时你已经退不回去了,说的粗俗点就是“你挂了”。


现在让你编一个程序,在一个给定的迷宫里面找到所有潜在可能的逃生路径,并将他们打印出来。注意:有可能会有环路哦!
要求:
        1、程序尽可能简练,算法的时间和空间复杂度没有强制要求,但要合情理。假如,你的程序处理1000个房间时,用了20多秒,那肯定是不合格的。
        2、将所有逃生路径全部输出,但不要重复输出相同的路径。
        3、程序必须能够正确处理可能存在的环路情况。


例如:


这个示例中有环路,编号为0的房间为出口处。
如果从房间号为127的格子出发,那么存在两条逃生路径。因此,你的程序应该输出像下面这样的结果:
starting in room 127
path found
    in 127 go south
    in 17 go south
    in 8 go south
    in 12 go west
    in 25 go west
outside


path found
    in 127 go south
    in 17 go west
    in 93 go south
    in 25 go west
outside

我的解法:

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <unistd.h>

  3. enum direction {
  4.     EAST,
  5.     WEST,
  6.     SOUTH,
  7.     NORTH,
  8.     DIR_NUM,
  9. };

  10. char *dir_str[DIR_NUM] = {"east", "west", "south", "north"};

  11. struct room {
  12.     int number;
  13.     enum direction open;
  14.     struct room *doors[DIR_NUM];
  15. };

  16. struct room rooms[10] = {
  17.     {    //0
  18.         .number = 4,
  19.         .open = DIR_NUM,
  20.         .doors = {NULL},
  21.     },
  22.     {    //1
  23.         .number = 127,
  24.         .open = DIR_NUM,
  25.         .doors = {rooms+2, NULL, rooms+4, NULL},        
  26.     },
  27.     {    //2
  28.         .number = 61,
  29.         .open = DIR_NUM,
  30.         .doors = {NULL, NULL, rooms+5, NULL},        
  31.     },
  32.     {    //3
  33.         .number = 93,
  34.         .open = DIR_NUM,
  35.         .doors = {rooms+4, NULL, rooms+7, rooms},        
  36.     },
  37.     {    //4
  38.         .number = 17,
  39.         .open = DIR_NUM,
  40.         .doors = {rooms+5, rooms+3, rooms+8, NULL},        
  41.     },
  42.     {    //5
  43.         .number = 43,
  44.         .open = DIR_NUM,
  45.         .doors = {rooms, NULL, NULL, NULL},        
  46.     },
  47.     {    //6
  48.         .number = 0,
  49.         .open = DIR_NUM,
  50.         .doors = {NULL},        
  51.     },
  52.     {    //7
  53.         .number = 25,
  54.         .open = DIR_NUM,
  55.         .doors = {rooms+8, rooms+6, NULL, rooms+3},        
  56.     },
  57.     {    //8
  58.         .number = 8,
  59.         .open = DIR_NUM,
  60.         .doors = {NULL, NULL, rooms+9, rooms+4},        
  61.     },
  62.     {    //9
  63.         .number = 12,
  64.         .open = DIR_NUM,
  65.         .doors = {rooms+5, rooms+7, NULL, rooms+8},        
  66.     },
  67. };
  68. int room_num = 10;

  69. int exit_room_number = 0;

  70. struct room *start_room = rooms+1;

  71. void print_path()
  72. {
  73.     struct room *start = start_room;

  74.     printf("path found\n");
  75.     while (start->open != DIR_NUM)
  76.     {
  77.         printf("\t in %d go %s.\n", start->number, dir_str[start->open]);
  78.         start = start->doors[start->open];
  79.     }
  80.     printf("outside\n\n");
  81. }

  82. void path_find(struct room *start)
  83. {
  84.     int i;    
  85.     
  86.     if ( start->number == exit_room_number)    
  87.     {
  88.         print_path();        
  89.         return;
  90.     }

  91.     if ( start->open != DIR_NUM)
  92.         return;
  93.         
  94.     if ( start->doors[EAST] != NULL)
  95.     {
  96.         start->open = EAST;        
  97.         path_find(start->doors[EAST]);        
  98.     }
  99.     
  100.     if ( start->doors[WEST] != NULL)
  101.     {
  102.         start->open = WEST;        
  103.         path_find(start->doors[WEST]);    
  104.     }

  105.     if ( start->doors[SOUTH] != NULL)
  106.     {
  107.         start->open = SOUTH;        
  108.         path_find(start->doors[SOUTH]);    
  109.     }
  110.     
  111.     if ( start->doors[NORTH] !=NULL)
  112.     {
  113.         start->open = NORTH;        
  114.         path_find(start->doors[NORTH]);    
  115.     }    
  116.     
  117.     start->open = DIR_NUM;    

  118.     return;    
  119.     
  120. }

  121. int main(int argc, char*argv[])
  122. {
  123.     
  124.     printf("starting in room %d\n", start_room->number);
  125.     path_find(start_room);
  126.     
  127.     return 0;
  128. }

阅读(3492) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~