蓝桥杯迷宫---c语言实现

题目

标题:迷宫

X星球的一处迷宫游乐场建在某个小山坡上。
它是由10x10相互连通的小房间组成的。

房间的地板上写着一个很大的字母。
我们假设玩家是面朝上坡的方向站立,则:
L表示走到左边的房间,
R表示走到右边的房间,
U表示走到上坡方向的房间,
D表示走到下坡方向的房间。

X星球的居民有点懒,不愿意费力思考。
他们更喜欢玩运气类的游戏。这个游戏也是如此!

开始的时候,直升机把100名玩家放入一个个小房间内。
玩家一定要按照地上的字母移动。

迷宫地图如下:

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

请你计算一下,最后,有多少玩家会走出迷宫?
而不是在里边兜圈子。

请提交该整数,表示走出迷宫的玩家数目,不要填写任何多余的内容。

如果你还没明白游戏规则,可以参看一个简化的4x4迷宫的解说图:

蓝桥杯迷宫---c语言实现

题目分析

这个问题是一个很典型的一个深度优先搜索,从一个点开始,直到出现回路或者走出迷宫,才会结束搜索并返回结果,这个过程我们可以使用一个递归来实现.

bool solve(int i, int j) {
    if (i < 0 || i > 9 || j < 0 || j > 9)//走出迷宫
        return true;
	
    if(vis[i][j] == 1)//出现回路
        return false;
	
    vis[i][j] = 1;//走过了就标记成1

    switch(data[i][j]){//根据房间的指示走向一个房间,也就是进入下一层递归
        case 'U':
            return solve(i-1,j);
        case 'D':
            return solve(i+1,j);
        case 'L':
            return solve(i,j-1);
        case 'R':
            return solve(i,j+1);
        default:
            return false;
    }
}

既然上面的代码是我们解决问题的方案,那么他需要的环境是什么呢?
首先flag这个需要置零,记录每一个点的轨迹的时候,都需要是一个没有使用过的地图。
我们可以使用一个循环嵌套来实现地图清零的操作

for(int i=0;i<10;i++)
	for(int j=0;j<10;j++)
		flag[i][j]=0;

完成清零之后还需要什么?对每次结果进行一个判断,细心的同学可能提前就发现了,我们解决问题的函数类型是bool类型,
也就是说再执行完递归函数之后,就已经把判断结果给我们了,所以,只需要一个if语句就可以判断是不是出去了迷宫。
解决了关键点之后,完整的代码如下:

#include <stdio.h>
#include <stdbool.h>

int ans;
int vis[10][10];//遍历数组.经过一次置1
char data[10][11]=
  {"UDDLUULRUL","UURLLLRRRU","RRUURLDLRD","RUDDDDUUUU",
  "URUDLLRRUU","DURLRLDLRL",
  "ULLURLLRDU","RDLULLRDDD","UUDDUDUDLL","ULRDLUURRR"};



bool solve(int i, int j) {
    if (i < 0 || i > 9 || j < 0 || j > 9)//走出迷宫
        return true;
	
    if(vis[i][j] == 1)//出现回路
        return false;
	
    vis[i][j] = 1;//走过了就标记成1

    switch(data[i][j]){//根据房间的指示走向一个房间,也就是进入下一层递归
        case 'U':
            return solve(i-1,j);
        case 'D':
            return solve(i+1,j);
        case 'L':
            return solve(i,j-1);
        case 'R':
            return solve(i,j+1);
        default:
            return false;
    }
}

int main(int argc, const char *argv[]) {

    for (int i = 0; i < 10; ++i) {//行
        for (int j = 0; j < 10; ++j) {//列


            for(int k=0;k<10;k++)//初始化
				for(int l=0;l<10;l++)
					vis[k][l]=0;
					 
            if (solve(i,j))
                ans++;
                
        }
    }

    printf("%d\n",ans);
    
    return 0;
}
上一篇:点分治


下一篇:ARCGIS制作三维地图教程(BIGEMAP)