标题： 迷宫问题
时 限： 100000 ms
内存限制： 100000 K
总时限： 300000 ms
描述： 迷宫问题
 
迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照 下,左,上,右 的顺序来搜索路径.
输入： 迷宫宽度w 迷宫高度h
迷宫第一行
迷宫第二行
...
迷宫第h 行
输出： 入口横坐标1  入口纵坐标1
横坐标2       纵坐标2
横坐标3       纵坐标3
横坐标4       纵坐标4
...
横坐标n-1    纵坐标n-1
出口横坐标n 出口纵坐标n
输入样例： 8 10
1 1 1 1 1 1 1 1
1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 0 3 1 0 1 1
1 0 0 1 0 0 4 1
1 0 0 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1
输出样例： 3 3
2 3
2 4
2 5
3 5
3 6
3 7
4 7
4 6
4 5
4 4
5 4
6 4
  
提示： 使用栈

 

#include <stdio.h>
#include <stdlib.h>

int visit(int, int);

int maze[7][7] = {{2, 2, 2, 2, 2, 2, 2},
                  {2, 0, 0, 0, 0, 0, 2},
                  {2, 0, 2, 0, 2, 0, 2},
                  {2, 0, 0, 2, 0, 2, 2},
                  {2, 2, 0, 2, 0, 2, 2},
                  {2, 0, 0, 0, 0, 0, 2},
                  {2, 2, 2, 2, 2, 2, 2}};

int startI = 1, startJ = 1;  // 入口
int endI = 5, endJ = 5;  // 出口
int success = 0;

int main(void) {
    int i, j;

    printf("显示迷宫：\n");
    for(i = 0; i < 7; i++) {
        for(j = 0; j < 7; j++)
            if(maze[i][j] == 2)
                printf("█");
            else
                printf("  ");
        printf("\n");
    }

    if(visit(startI, startJ) == 0)
        printf("\n没有找到出口！\n");
    else {
        printf("\n显示路径：\n");
        for(i = 0; i < 7; i++) {
            for(j = 0; j < 7; j++) {
                if(maze[i][j] == 2)
                    printf("█");
                else if(maze[i][j] == 1)
                    printf("◇");
                else
                    printf("  ");
            }
            printf("\n");
        }
    }

    return 0;
}

int visit(int i, int j) {
    maze[i][j] = 1;

    if(i == endI && j == endJ)
        success = 1;

    if(success != 1 && maze[i][j+1] == 0) visit(i, j+1);
    if(success != 1 && maze[i+1][j] == 0) visit(i+1, j);
    if(success != 1 && maze[i][j-1] == 0) visit(i, j-1);
    if(success != 1 && maze[i-1][j] == 0) visit(i-1, j);

    if(success != 1)
        maze[i][j] = 0;
   
    return success;
}  
自己改下吧 思路应该差不多的

可以搜一下回溯算法

谢谢啦哥们

呵呵

难得在编程论坛看到一个优秀的代码， 学习一下，

作者：鬼鬼千年
#include<stdio.h>
int maze[10][10] = {
        {1,1,1,1,1,1,1,1,1,1},
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,0,0,1,1,0,0,1},
        {1,0,1,1,1,0,0,0,0,1},
        {1,0,0,0,1,0,0,0,0,1},
        {1,0,1,0,0,0,1,0,0,1},
        {1,0,1,1,1,0,1,1,0,1},
        {1,1,1,0,0,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,1,1}};/*初始化迷宫*/
int mark[10][10] = {0};/*初始化标志位,0代表没走过,1代表走过*/

/*方向*/
typedef struct{
    short int vert;
    short int horiz;
}offsets;

offsets move[4] = {{0,1},{1,0},{0,-1},{-1,0}};/*北,东,南,西*/


/*迷宫类型*/
typedef struct element{
    short int row;
    short int col;
    short int dir;
}element;

element stack[100];


void path(void);
  element del(int* top);
void add(int* top,element item);


element del(int* top)/*出栈,top指向栈顶元素*/
{
    if(*top == -1)
    {
        printf("stack is empty!\n");
    }
    return stack[(*top)--];
}



void add(int* top,element item)/*入栈*/
{
    if(*top >= 100)
    {
        printf("stack is full!\n");
        return;
    }
    stack[++*top] = item;
}


void path(void)/*迷宫函数*/
{
    element position;
    int i,row,col,next_row,next_col,dir,top;
    int found = 0;
    mark[1][8] = 1,top = 0;/*初始化标志数组元素以及栈*/
    stack[0].row = 1,stack[0].col = 8,stack[0].dir = 0;
    while(top > -1 && !found)
    {
          position= del(&top);  /*将栈顶元素取出,*/
        row = position.row;            /*利用中间变量row,col,dir等候判断*/
        col = position.col;
        dir = position.dir;
        while(dir < 4 && !found)
        {
            next_row = row + move[dir].vert;
            next_col = col + move[dir].horiz;
            if(row == 7 && col == 1)
                found = 1;
            else if(!maze[next_row][next_col] && !mark[next_row][next_col])/*判断下一步可走并且没走过,则入栈*/
                    {
                        mark[next_row][next_col] = 1;
                        position.row = row;
                        position.col = col;
                        position.dir = ++dir;
                        add(&top,position);/*合理则入栈*/
                        row = next_row;/*继续向下走*/
                        col = next_col;dir = 0;
                    }
                    else
                        dir++;/*dir<4时,改变方向*/
      
        }
        if(found)/*判断是否有出口*/
        {
            printf("the path is:\n");
            printf("row col\n");
            for(i = 0;i <= top;++i)
                printf("(%2d,%5d)",stack[i].row,stack[i].col);
                printf("(%2d,%5d)\n",7,1);
            
            
        }
         
            
    }
    if(found==0)
        printf("没有路径\n");
}


int main(void)
{   
    path();
     
return 0;
}

  这个程序不错，改改的话我可以拿去做课程设计了 哈哈谢谢啦

这个能不能加个三元组输出

小白来瞧瞧

大神能不能帮忙解释一下迷宫算法中的Pass，Footprint,Markprint算法？