迷宫问题

不过该算法得出的解法并不是最简解法，因为该算法是根据数组next的顺序来进行先后查找的，即先查找右边，再查找下边，再查找左边，最后查找上边。

下面是深度优先搜索基本模型。

void dfs(int step)
{
    判断边界;
    for (i=1;i<=n;i++)尝试每一种可能
    {
        dfs(step+1);
    }
    返回 
}

BUG已改正，无解情况已增加。

/* S010 0000 0010 01E0 0001 S011 0011 1111 1111 111E */
#include<stdio.h>
#include<string.h>
#define m 5//地图大小 
#define n 4
int count=0;
int flag[m][n],s[m*n][2],next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//右下左右
char map[m][n];
int dfs(int i,int j)
{
    int i1,j1,k;
    for (k=0;k<4;k++)
    {
        i1=i+next[k][0];
        j1=j+next[k][1];
        if (i1<0||i1>=m||j1<0||j1>=n)
        continue;
        //判断是否到达终点
        if (map[i1][j1]=='E')
        {
            s[count][0]=i1;
            s[count][1]=j1;
            count++;
            return 0;
        }
        if (map[i1][j1]=='0'&&flag[i1][j1]==0)
        {
            s[count][0]=i1;
            s[count][1]=j1;
            count++;
            flag[i1][j1]=1;
            //若到达终点，则前面的都不用删除
            if (dfs(i1,j1)==0)
            return 0;
            //否则
            flag[i1][j1]=0;
            s[count][0]=0;
            s[count][1]=0;
            count--;
        }
    }
    return 1;
}
int main()
{
    int i,j;
    printf("请输入一个迷宫地图\n0代表可走路径\n1代表障碍物\nS代表起点\nE代表终点:\n");
    for (i=0;i<m;i++)
    gets(map[i]);
    for (i=0;i<m;i++)
    {
        for (j=0;j<n;j++)
        {
            if (map[i][j]=='S')
            {
                s[count][0]=i;
                s[count][1]=j;
                count++;
                dfs(i,j);
            }
        }
    }
    if (count==1)
    printf("该地图无解");
    else
    {
        printf("该地图的解法之一如下\n");
        for (i=0;i<count;i++)
        printf("%d %d\n",s[i][0],s[i][1]);
        printf("总共走了%d步",count-1);
    }
}