天花板编程手把手计划-第1期-第2天

题目

如图所示，有一个6 * 6的迷宫，左上角为入口，右下角为出口。图中0的位置可以走，1的位置不能走。请编程找出唯一的一条通过迷宫的路。

图片.png

解题思路

1.题目为6*6矩阵表示的迷宫，在矩阵四周加入1，忽略边界问题方便使用
2.用1234分别表示方向上、右、下、左。当判断下个路径可走的时候，根据进入该路径的方向设置改路径进入下一个路径的方向。即按照你所面对的方向的左侧。判断是失败的时候顺时针转变方向。（：不懂你在说什么 ：额，表述能力有限，哈哈）
3.当判断下个路径可走的时候，将改路径的值加上2作为标记。并将下个路径的位置设置为当前路径。

图片.png

如图当你面对的方向不同的时候，你的左面在平面图上的方位不同，当左左面行不通的时候，顺时针改变方向，直到左面是通的。这种思路在迷宫可解的时候走到出口，不通的时候会回到原点。

源码

#include <stdio.h>

#define UPP 1
#define LOW 3
#define LEF 4
#define RIG 2

struct weizhi{
    int x;
    int y;
    int s;
};
weizhi NextWeizhi(weizhi now)
{
    weizhi next1;
    int x = now.x;
    int y = now.y;

    switch (now.s)
    {
        case 1: {
            next1.x = x - 1;
            next1.y = y;
            break;
        }

        case 2: {
            next1.x = x;
            next1.y = y + 1;
            break;
        }

        case 3: {
            next1.x = x + 1;
            next1.y = y;
            break;
        }

        case 4: {
            next1.x = x;
            next1.y = y - 1;
            break;
        }
        default:break;
    }

    return next1;
}

int main()
{
    int i, j;

    //定义数组 在四周加上边界
    int maze[8][8] = {
    1,1,1,1,1,1,1,1,
    1,0,1,0,1,1,1,1,
    1,0,0,0,1,0,1,1,
    1,0,1,1,0,0,0,1,
    1,0,1,1,0,1,0,1,
    1,0,0,0,0,1,0,1,
    1,0,1,0,1,1,0,1,
    1,1,1,1,1,1,1,1
    };
    //输出打印迷宫
    printf("这是原来的\n");
    for (i = 1; i < 7; i++)
    {
        for (j = 1; j < 7; j++)
        {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
    //
    weizhi now, next;
    now.x = 1;
    now.y = 1;
    now.s = RIG;

    do {
            next = NextWeizhi(now);
            if (maze[next.x][next.y] != 1)
            {
                maze[now.x][now.y] = maze[now.x][now.y] + 2;
                now.x = next.x;
                now.y = next.y;

                if (now.s > 1)
                {
                    now.s--;
                }
                else 
                {
                    now.s = 4;
                }
            }
            else
            {
                if (now.s < 4)
                {
                    now.s++;
                }
                else
                {
                    now.s = 1;
                }

            }
    } while ( (now.x != 6)||(now.y != 6) );
    //此处有点绕，原来写的是与，发现不对后改成的或
    //输出打印迷宫
    printf("迷宫的解\n");
    for (i = 1; i < 7; i++)
    {
        for (j = 1; j < 7; j++)
        {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }

    

    return 0;
}

执行结果

图片.png

总结

图中的2表示走过一遍，4位走过两遍。出口判断有带点问题，最后一个没更改。暂时想到这么多。