湛江网站建设与网页,一个人能建设一个公司网站吗,口碑营销的案例及分析,定制logo题目
试题编号#xff1a; 201312-5 试题名称#xff1a; I’m stuck! 时间限制#xff1a; 1.0s 内存限制#xff1a; 256.0MB 问题描述#xff1a; 问题描述 给定一个R行C列的地图#xff0c;地图的每一个方格可能是’#’, ‘’, ‘-’, ‘|’, ‘.’, ‘S’, ‘…题目
试题编号 201312-5 试题名称 I’m stuck! 时间限制 1.0s 内存限制 256.0MB 问题描述 问题描述 给定一个R行C列的地图地图的每一个方格可能是’#’, ‘’, ‘-’, ‘|’, ‘.’, ‘S’, ‘T’七个字符中的一个分别表示如下意思 ‘#’: 任何时候玩家都不能移动到此方格 ‘’: 当玩家到达这一方格后下一步可以向上下左右四个方向相邻的任意一个非’#‘方格移动一格 ‘-’: 当玩家到达这一方格后下一步可以向左右两个方向相邻的一个非’#‘方格移动一格 ‘|’: 当玩家到达这一方格后下一步可以向上下两个方向相邻的一个非’#‘方格移动一格 ‘.’: 当玩家到达这一方格后下一步只能向下移动一格。如果下面相邻的方格为’#’则玩家不能再移动 ‘S’: 玩家的初始位置地图中只会有一个初始位置。玩家到达这一方格后下一步可以向上下左右四个方向相邻的任意一个非’#‘方格移动一格 ‘T’: 玩家的目标位置地图中只会有一个目标位置。玩家到达这一方格后可以选择完成任务也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非’#‘方格移动一格。 此外玩家不能移动出地图。 请找出满足下面两个性质的方格个数 1. 玩家可以从初始位置移动到此方格 2. 玩家不可以从此方格移动到目标位置。 输入格式 输入的第一行包括两个整数R 和C分别表示地图的行和列数。(1 ≤ R, C ≤ 50)。 接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个’S’和一个’T’。 输出格式 如果玩家在初始位置就已经不能到达终点了就输出“I’m stuck!”不含双引号。否则的话输出满足性质的方格的个数。 样例输入 5 5 –± …|#. …|## S-±T ####. 样例输出 2 样例说明 如果把满足性质的方格在地图上用’X’标记出来的话地图如下所示 --± …|#X …|## S-±T ####X
题目分析个人理解
此题一看就是走迷宫的题目能否到达可以联想为小鼠走迷宫题目要求输出的值满足两个条件1. 玩家可以从初始位置移动到此方格2. 玩家不可以从此方格移动到目标位置。总结一句也就是输出小鼠可以到达且不是终点的位置有几个。如果找不到出口 就输出‘I’m stuck!’。首先想到DFS算法注意此题不同的是T即是终点也可选择作为起点而S只能是起点根据题目先建立一个长为r宽为c的画布地图 接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个’S’和一个’T’ 还是选择二维列表作为存储器。使用.append()方法追加写入创建地图matrix)遍历地图找到初始出发点S和终点T并记录。dfs算法本身原理就是基于递归算法的现在定义两个函数第一个是关于S此函数表示从S出发能够到达的坐标点全部用一张新图记录如果能够到达那就将新画布对应的坐标位置的值设置为1如果到达不了就是默认值0画布是初始值为0的二维列表。下面进入条件判断的环节dfs算法的代码结构就是在函数体内调用自己的一个子函数实现递归在子函数内设置判断条件如果原画布是’#‘就说明到不了墙壁子函数的作用是将能够到达的点全部标记为1下面进入判断如果是ST就可以上下左右都可以移动如果是’|‘只能上下移动如果是’-‘只能左右移动’.‘只能向下移动。移动的判断条件有两个第一个是不能超出地图第二个是值为0的地方表示没走到过现在用子函数来标记能够走到的就标记为1尤其注意即使不是#也有可能到达不了在函数S的画布中标记了所有从S出发后能够到达的所有方格标记为1只需要把T点带入如果值为1则能到达如果值为0我就输出‘I’m stuck!’。下面再仔细读题到达T后可以选择结束游戏也可以继续那么此时T就成了起点那么还得再定义一个函数T和函数S一样再做一个画布和S同样操作将从T出发能够到达的所有格子全部标记1。如果从S出发能到达T就请找出满足下面两个性质的方格个数 1. 玩家可以从初始位置移动到此方格 2. 玩家不可以从此方格移动到目标位置。那么一句话就是求在S画布中标记在画布T中未标记的方格有几个。只需要一个计数器初始值为0满足上面条件加1即可。上代码
# input
line input()
nums line.split()
R eval(nums[0])
C eval(nums[1])
matrix []
for i in range(R):matrix.append(input())
# print(R,C)
# print(matrix)# find S and T
for i in range(R):for j in range(C):if matrix[i][j] S:xS, yS i, j
for i in range(R):for j in range(C):if matrix[i][j] T:xT, yT i, j# traverse from Sdef traverseS():def inner(x, y):if matrix[x][y] #:returnres[x][y] 1if x R - 1 and matrix[x][y] in ST|. and res[x 1][y] 0:inner(x 1, y)if x 0 and matrix[x][y] in ST| and res[x - 1][y] 0:inner(x - 1, y)if y C - 1 and matrix[x][y] in ST- and res[x][y 1] 0:inner(x, y 1)if y 0 and matrix[x][y] in ST- and res[x][y - 1] 0:inner(x, y - 1)res [[0 for i in range(C)] for j in range(R)]inner(xS, yS)return res# traverse from T reversely
def traverseT():def inner(x, y):if matrix[x][y] #:returnres[x][y] 1if x R - 1 and matrix[x 1][y] in ST| and res[x 1][y] 0:inner(x 1, y)if x 0 and matrix[x - 1][y] in ST|. and res[x - 1][y] 0:inner(x - 1, y)if y C - 1 and matrix[x][y 1] in ST- and res[x][y 1] 0:inner(x, y 1)if y 0 and matrix[x][y - 1] in ST- and res[x][y - 1] 0:inner(x, y - 1)res [[0 for i in range(C)] for j in range(R)]inner(xT, yT)return res# main
propt1 traverseS()
propt2 traverseT()
if propt1[xT][yT] 0:print(Im stuck!)
else:count 0for i in range(R):for j in range(C):if propt1[i][j] 1 and propt2[i][j] 0:count 1print(count)举一反三
下面用一道蓝桥杯的题目练手 样例输出 代码如下
总结 大学问
知道什么叫天高地厚
内心的天空 也要懂得探究
知道什么是海市蜃楼
人海的感受 也要去进修
知识跟世界细水长流
智慧用思考照明宇宙
我们懂得学问没尽头
学会怎么做事 再学做人的操守
我们懂得学习的理由
吸收是为了奉献 才能承先启后
生命不止坚毅与奋斗
有梦想才是 有意义的追求
成功不止付出与拥有
有承担才是 最高的成就
知识跟世界细水长流
智慧用思考照明宇宙
我们懂得学问没尽头
学会怎么自救 再学做人的操守
我们懂得学习的理由
力量要用来分享 才能承先启后
我们懂得学问没尽头
学会终身学习 才没辜负一番造就
我们懂得学习的理由
活出生命的光彩 才无愧于春秋
