递归回溯—走迷宫

前言

你知道我这个迷宫走了多久嘛！！！！！！！！！！！！！！！！！！！！！！！！！！！

题目介绍

输入样例:

5 4
1 1 0 0
1 1 1 1
0 1 1 0
1 1 0 1
1 1 1 1
1 1
5 4

输出样例:

(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)

在开始之前大家可以先自己写一下看一下能不能自己写出来~注意输出的格式哦！

分析

这个题和之前的那个八皇后问题差不多一个思路，就是一个递归回溯问题，非常简单啦！！

就上下左右走走过去就标记0走不了了，如果这些都走完，我们就回溯就好了，很简单的啦

理论存在，实践开始！

代码：

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

struct node
{
    int x;
    int y;
}pa[10010];
int ed1,ed2;
int a[17][17];
int count1=0;int m1,n1;
void path (int m,int n,int num);
void path (int m,int n,int num)
{
    int i,j;

    if(m==ed1&&n==ed2)
    {
        count1=-1;
        for (i=1;i<num;i++)
        {
            printf("(%d,%d)->",pa[i].x,pa[i].y);
        }
        printf("(%d,%d)",ed1,ed2);
        printf("\n");
    }

    pa[num].x=m,pa[num].y=n;

    if(a[m][n-1]==1&&m>=1){a[m][n]=0;path(m,n-1,num+1);a[m][n]=1;}
    if(a[m-1][n]==1&&m>=1){a[m][n]=0;path(m-1,n,num+1);a[m][n]=1;}
    if(a[m][n+1]==1&&m>=1){a[m][n]=0;path(m,n+1,num+1);a[m][n]=1;}
    if(a[m+1][n]==1&&m>=1){a[m][n]=0;path(m+1,n,num+1);a[m][n]=1;}




}
int main()
{
    int st1,st2;
    int i,j;

    while(scanf("%d%d",&m1,&n1)!=EOF)
    {
        count1=0;
    memset(a,0,sizeof(a));
    for (i=1;i<=m1;i++)
    {
        for (j=1;j<=n1;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d%d%d%d",&st1,&st2,&ed1,&ed2);
    path(st1,st2,1);

        if(count1!=-1)
    {
        printf("-1\n");
    }
    }

}

注意事项： 

1.memset(a,0,sizeof(a));要在while里面

2.

 这个地方要随机应变，因为这个地方的顺序不同输出结果不同，然后这个地方如果嫌弃我写的麻烦你也可以设两个0-101的数组来控制xy坐标

3.我这个题if后面不小心写了一个；卡了好长时间大家不要学我傻！！

4.这个题的坐标要用到结构体来存路径比较方便！！恩恩！以后要学会这个方法

Love is worth years.❤
热爱可抵岁月漫长。