本文主要是介绍【python】屈小原求三峡大学面积（CTGU百年校庆），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
"""
题目描述：
屈小原希望你能帮他求出一块地图中学校的面积。地图由nxm个方格组成，每个方格中都有一个小写的英文字母，如果该方格为学校所属，那么该方格必定是一段连续的ctgu的组成部分。从一个特定的字符开始，可以向上、下、左、右四个方向移动到相邻的方格。如果按照这种方式，能够从一个字符按顺序走到另一个字符，形成指定的字符串序列（在这个情况下是“ctgu”），那么这些方格被认为是连续的，即它们是学校的一部分。
输入：
第一行包含两个整数n，m(1<n,m<1000)-地图的大小。接下来的n行包含m个小写字母，描述指定的地图
输出：
对于每组测试数据，输出学校所占的方格数目。
样例1：
4 4
cbug
tgtc
gutc
cgtu
样例输出：
7
"""
代码：
"""
思路：深度优先搜索（DFS）
"""
N = 1000 # 设置二维数组的最大维度。预分配空间
# 在绝大多数情况下，上下左右移动的坐标变化确实应该是 (0, 1)、(0, -1)、(1, 0) 和 (-1, 0)。
dx = [0, 0, 1, -1] # 定义了在x方向上的四个可能的移动（上下左右）
dy = [1, -1, 0, 0] # 定义了在y方向上的四个可能的移动
ctgu = "ctgu" # 目标字符串
# 初始化一个二维字符数组s，用于存储输入的字符数据
s = [['' for _ in range(N)] for _ in range(N)]
# 初始化一个二维访问数组vis，用于标记某个位置是否被访问过
vis = [[0 for _ in range(N)] for _ in range(N)]def dfs(x, y, stk):u = len(stk) # 获取当前堆栈的大小if u == 4: # 如果堆栈大小为4，标记堆栈中所有位置为已访问，并终止搜索for i in range(4):# 元组，stk[i][0]表示第i个位置的x坐标，stk[i][1]表示第i个位置的y坐标vis[stk[i][0]][stk[i][1]] = 1returnfor i in range(4): # 循环遍历四个可能的方向tx = x + dx[i] # 计算新的x位置ty = y + dy[i] # 计算新的y位置# 检查新位置是否在边界内，堆栈大小是否小于目标字符串的长度，和新位置的字符是否匹配目标字符串的当前字符if 0 <= tx < n and 0 <= ty < m and u < len(ctgu) and s[tx][ty] == ctgu[u]:# 如果满足条件，将新位置元组(tx, ty)添加到堆栈中stk.append((tx, ty))dfs(tx, ty, stk) # 递归调用DFS函数stk.pop() # 回溯：从堆栈中弹出最后一个位置 返回的是地图坐标n, m = map(int, input().split()) # 输入n和m的值
for i in range(n):s[i] = list(input()) # 将输入的字符串转换为字符列表，并赋值给s数组的对应行
for i in range(n):for j in range(m):stk = [] # 初始化一个空堆栈dfs(i, j, stk) # 从位置(i, j)开始执行DFSans = 0 # 初始化答案变量为0
for i in range(n):for j in range(m):if vis[i][j]: # 如果位置(i, j)被访问过，增加答案变量ans += 1
print(ans) # 输出最终答案
这篇关于【python】屈小原求三峡大学面积（CTGU百年校庆）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
