算法学习，记录 day1

2017蓝桥杯初赛-迷宫

题目描述

X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。 房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则： L表示走到左边的房间，R表示走到右边的房间，U表示走到上坡方向的房间，D表示走到下坡方向的房间。 X星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！ 开始的时候，直升机把100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。 迷宫地图如下：

-———– \n UDDLUULRUL \n UURLLLRRRU \n RRUURLDLRD \n RUDDDDUUUU \n URUDLLRRUU \n DURLRLDLRL \n ULLURLLRDU \n RDLULLRDDD \n UUDDUDUDLL \n ULRDLUURRR \n -———– \n

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

输出

输出一个整数表示答案

提示

为方便理解，可参考此图

img
img

题目分析

暴力：

  1. 给出100个点，一个点一个点，进行手动做，几分钟可以AC

DFS:

对于每一个点，进行DFS，知道走出边界为止。

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#!/usr/bin/env python
# -*- coding: utf-8 -*-

map = 'UDDLUULRULUURLLLRRRURRUURLDLRDRUDDDDUUUUURUDLLRRUUDURLRLDLRLULLURLLRDURDLULLRDDDUUDDUDUDLLULRDLUURRR'


map_list = [['#' for i in range(12)] for i in range(12)]
for i in range(1,11):
    map_list[i][1:11] = map[(i-1)*10:(i-1)*10 +10]
print(map_list)


def dfs(i, j):
    global s
    if via[i][j]: return
    via[i][j] = 1
    if map_list[i][j] == '#':
        s += 1
        return
    else:
        if  map_list[i][j] == 'L':
            dfs(i, j-1)
        if map_list[i][j] == 'R':
            dfs(i, j+1)
        if map_list[i][j] == 'U':
            dfs(i-1, j)
        if map_list[i][j] == 'D':
            dfs(i+1, j)

s = 0
for i in range(1, 11):
    for j in range(1, 11):
        via = [[0 for j in range(12)] for j in range(12)] #设置访问记录点，对于一个初始点来说，每层dfs访问过的点都置为1,防止在里面兜圈子。
        dfs(i, j)
print(s)